Cod sursa(job #633321)

Utilizator andumMorie Daniel Alexandru andum Data 13 noiembrie 2011 16:10:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int nmax = 100005;

int n,m,i,x,y,viz[nmax],viz2[nmax],k;
vector <int> G[nmax],Gt[nmax],Gs[nmax],s;
vector <int>::iterator it;

void DF(int k)
{
    vector <int>::iterator it;
    viz[k]=1;
    if (!G[k].empty())
    for (it=G[k].begin();it!=G[k].end();it++)
        if (!viz[*it])
            DF(*it);
    s.push_back(k);
}

void DFt(int x)
{
    vector <int>::iterator it;
    viz2[x]=k;
    if (!Gt[x].empty())
    for (it=Gt[x].begin();it!=Gt[x].end();it++)
        if (viz2[*it]==-1)
            DFt(*it);
}

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);
        x--; y--;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }

    for (i=0;i<n;i++)
        if (!viz[i])
            DF(i);
    fill(viz2,viz2+n,-1);
    for (; s.size(); s.pop_back())
        if (viz2[s.back()]==-1)
        {
            DFt(s.back());
            k++;
        }
    printf("%d\n", k);
    for (i=0;i<n;i++)
        Gs[viz2[i]].push_back(i);
    for (i=0;i<k;i++)
    {
        for (it=Gs[i].begin();it!=Gs[i].end();it++)
            printf("%d ", *it+1);
        printf("\n");
    }

    return 0;
}