Cod sursa(job #901829)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 1 martie 2013 11:51:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<cstdio>
#include<vector>
#define INF 100001

using namespace std;

bool used1[INF],used2[INF];
vector<int> graph1[INF],graph2[INF];
vector<int> Q;
vector<int> ras[INF];
int n,m,nr=0;

void df1(int nod)
{
    if(used1[nod])return;
    used1[nod]=1;
    for(int i=0;i<graph1[nod].size();++i)
    {
        int nod2=graph1[nod][i];
        df1(nod2);
    }
    Q.push_back(nod);
}

void df2(int nod)
{
    if(used2[nod])return;
    used2[nod]=1;
    ras[nr].push_back(nod);
    for(int i=0;i<graph2[nod].size();++i)
        df2(graph2[nod][i]);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graph1[x].push_back(y);
        graph2[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!used1[i])df1(i);

     while(Q.size()>0)
     {
         int nod=Q.back();
         if(!used2[nod])
         {
             ++nr;
             df2(nod);
         }
         Q.pop_back();
     }
     printf("%d\n",nr);
     for(int i=1;i<=nr;++i)
     {
         for(int j=0;j<ras[i].size();++j)printf("%d ",ras[i][j]);
         printf("\n");
     }
     return 0;
}