Cod sursa(job #1517142)

Utilizator AdrianGotcaAdrian Gotca AdrianGotca Data 3 noiembrie 2015 21:43:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

FILE *f=freopen("ctc.in","r",stdin);
FILE *g=freopen("ctc.out","w",stdout);

vector <int> G[100001],GT[100001],S[100001],o;
int n,m,viz[100001],sol;
void read();
void DFS(int);
void DFST(int);
void solve();
void write();
int main(){
    read();
    solve();
    write();
}

void read(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void solve(){
    for (int i=1;i<=n;i++){
        if (!viz[i]){
            DFS(i);
        }
    }
    memset(viz,0,sizeof(viz));
    for (int i=o.size()-1;i>=0;i--){
        if (!viz[o[i]]){
            sol++;
            DFST(o[i]);
        }
    }
}

void DFS(int x){
    viz[x]=1;
    for (int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if (!viz[y]){
            DFS(y);
        }
    }
    o.push_back(x);
}

void DFST(int x){
    viz[x]=1;
    S[sol].push_back(x);
    for (int i=0;i<GT[x].size();i++){
        int y=GT[x][i];
        if (!viz[y]){
            DFST(y);
        }
    }
}

void write(){
    printf("%d\n",sol);
    for (int i=1;i<=sol;++i){
        for (int j=0;j<S[i].size();j++){
            printf("%d ",S[i][j]);
        }
        printf("\n");
    }
}