Cod sursa(job #796394)

Utilizator idomiralinIdomir Alin idomiralin Data 11 octombrie 2012 13:12:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
# include <cstdio>
# include <vector>

using namespace std;

vector <int> sol[100005], G[100005], GT[100005];
int ct, ct1, viz[100005], A[100005];

void dfs(int nod)
{
     int i, vec;
     
     viz[nod] = 1;
     for (i = 0; i < G[nod].size(); i++)
     {
         vec = G[nod][i];
         if (!viz[vec]) dfs(vec);
         }
     
     A[++ct1] = nod;
}
         
void dfs2(int nod)
{
     int i, vec;
     
     sol[ct].push_back(nod);
     viz[nod] = 1;
     
     for (i = 0; i < GT[nod].size(); i++)
     {
         vec = GT[nod][i];
         if (!viz[vec]) dfs2(vec);
         }
}

int n, m, a, b;
int main()
{
    int i, j;
    
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        GT[b].push_back(a);
        }
        
    for (i = 1; i <= n; i++)
        if (!viz[i]) dfs(i);
        
    memset(viz, 0, sizeof(viz));
        
    for (i = n; i >= 1; i--)
        if (!viz[A[i]]){
                  ct++;
                  dfs2(A[i]);
                  }
        
        printf("%d\n",ct);          
    for (i = 1; i <= ct1; i++)
    {
        for (j = 0; j < sol[i].size(); j++)
               printf("%d ",sol[i][j]);
               printf("\n");
               }
               
return 0;
}