Cod sursa(job #1813601)

Utilizator RaduToporanRadu Toporan RaduToporan Data 23 noiembrie 2016 08:13:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>

using namespace std;
int n,m,i,j,x,y,k,cmp,st[100005];
vector <int> sol[100005],v1[100005],v2[100005];
bool viz1[100005],viz2[100005];

void dfs1(int x)
{
    viz1[x]=1;
    for (int i=0; i<v1[x].size(); i++)
        if (viz1[v1[x][i]]==0)
        dfs1(v1[x][i]);
    st[++k]=x;
}

void dfs2(int x)
{
    viz2[x]=1;
    sol[cmp].push_back(x);
    for (int i=0; i<v2[x].size(); i++)
        if (viz2[v2[x][i]]==0)
        dfs2(v2[x][i]);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for (i=1; i<=n; i++)
        if (viz1[i]==0)
        dfs1(i);
    while (k!=0)
    {
        x=st[k];
        k--;
        if (viz2[x]==0)
        {
            cmp++;
            dfs2(x);
        }
    }
    printf("%d\n",cmp);
    for (i=1; i<=cmp; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}