Cod sursa(job #919167)

Utilizator thebest001Neagu Rares Florian thebest001 Data 19 martie 2013 14:18:49
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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=1;i<=n;i++){
        if (viz[i]){
            nr++;
            normal[nr].clear();
            DFST(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;
}