Cod sursa(job #919486)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 18:03:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <vector>
#define MAXN 100001
int n,m;
std::vector<int> normal[MAXN];
std::vector<int> transp[MAXN];
 
bool viz[MAXN];
 
int nr=0;
 
std::vector<int> oups;
 
void DFS(int x){
    viz[x]=true;
    for (int i=0;i<normal[x].size();i++){
        if (!viz[normal[x][i]]){
            DFS(normal[x][i]);
        }
    }
    oups.push_back(x);
}
 
void DFST(int x){
    viz[x]=false;normal[nr].push_back(x);
    for (int i=0;i<transp[x].size();i++){
        if (viz[transp[x][i]]){
            DFST(transp[x][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);
        normal[x].push_back(y);
        transp[y].push_back(x);
    }
 
    for (int i=1;i<=n;i++){
        if (!viz[i]){
            DFS(i);
        }
    }
 
    for (int i=oups.size();i>=0;i--){
        if (viz[oups[i]]){
            nr++;
            normal[nr].clear();
            DFST(oups[i]);
        }
    }
    printf("%d\n",nr);
    for (int i=1;i<=nr;i++){
        for (int j=0;j<normal[i].size();j++)
            printf("%d ",normal[i][j]);
        printf("\n");
    }
    return 0;
}