Cod sursa(job #2223594)

Utilizator PruteanuTheoPruteanu Theodor PruteanuTheo Data 20 iulie 2018 18:46:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int NMAX=100005;

vector <int> G[NMAX];
vector <int> GT[NMAX];

vector <int> sol[NMAX];
vector <int> viz;
stack <int> st;

int cc=0;

void dfs1(int u){
    viz[u]=1;
    for(int i=0;i<G[u].size(); ++i){
        int v=G[u][i];
        if(viz[v]==0)
            dfs1(v);
    }
    st.push(u);
}

void dfs2(int u){
    viz[u]=1;
    for(int i=0;i<GT[u].size(); ++i){
        int v=GT[u][i];
        if(viz[v]==0)
            dfs2(v);
    }
    sol[cc].push_back(u);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m;
    int u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        GT[v].push_back(u);
    }
    viz.assign(n+1,0);
    for(int i=1;i<=n;++i)
        if(viz[i]==0)
            dfs1(i);
    viz.clear();
    viz.assign(n+1,0);
    while(!st.empty()){
        if(viz[st.top()]==0){
            ++cc;
            dfs2(st.top());
        }
        st.pop();
    }
    printf("%d\n",cc);
    for(int i=1;i<=cc;++i){
        for(int j=0; j<sol[i].size();++j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}