Cod sursa(job #2102864)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 9 ianuarie 2018 15:55:01
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int>::iterator it;
vector <int> comp[100001],vecin[100001],wecin[100001];
int n,m,i,j,c,mns[100001],pls[100001];
void dfs_pls(int k)
{
    int i;
    pls[k]=c;
    for(i=0;i<vecin[k].size();i++)
        if(pls[vecin[k][i]]!=c)
            dfs_pls(vecin[k][i]);
}
void dfs_mns(int k)
{
    int i;
    mns[k]=c;
    for(i=0;i<wecin[k].size();i++)
        if(mns[wecin[k][i]]!=c)
        {
            if(pls[wecin[k][i]]==c)
                comp[c].push_back(wecin[k][i]);
            dfs_mns(wecin[k][i]);
        }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    while(m)
    {
        scanf("%d %d\n",&i,&j);
        if(i!=j)
        {
            vecin[i].push_back(j);
            wecin[j].push_back(i);
        }
        m--;
    }
    for(i=1;i<=n;i++)
        if((!mns[i]) || (!pls[i]))
        {
            c++;
            comp[c].push_back(i);
            dfs_pls(i);
            dfs_mns(i);
        }
    printf("%d\n",c);
    for(i=1;i<=c;i++,printf("\n"))
        for(it=comp[i].begin();it!=comp[i].end();it++)
            printf("%d ",*it);
    return 0;
}