Cod sursa(job #995364)

Utilizator assa98Andrei Stanciu assa98 Data 8 septembrie 2013 19:20:16
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <algorithm> 
using namespace std;

const int MAX_N=100100;

vector<int> A[MAX_N];
int viz[MAX_N],hmin[MAX_N],h[MAX_N];

int st[MAX_N];

int num;

vector< vector<int> > sol;

void get_ctc(int nod) {
    vector<int>ans;
    
    int nact;
    do {
        nact=st[st[0]];
        ans.push_back(nact);
        st[0]--;
    } while( st[0] && nact!=nod);

    sol.push_back(ans);
}

void dfs(int nod) {
    viz[nod]=1;
    h[nod]=++num;
    hmin[nod]=h[nod];
    st[++st[0]]=nod;
    for(vector<int>::iterator it=A[nod].begin(); it!=A[nod].end(); it++) {
        if(!viz[*it]) {
            dfs(*it);
            hmin[nod]=min(hmin[nod],hmin[*it]);
        }
        else if(viz[*it]==1) {
            hmin[nod]=min(hmin[nod],hmin[*it]);
        }
    }

    if(hmin[nod]==h[nod]) {
        get_ctc(nod);
    }
}

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        A[x].push_back(y);
    }
    
    for(int i=1;i<=n;i++) {
        if(!viz[i]) {
            dfs(i);
        }
    }

    printf("%d\n",sol.size());
    for(int i=0;i<sol.size();i++,printf("\n")) {
        for(vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); it++) {
            printf("%d ",*it);
        }
    }
  
    return 0;
}