Cod sursa(job #1352462)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 21 februarie 2015 12:36:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#define nmax 100010
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

void read();
void tarjan(long);
void sol();

long n,m;
vector < long > graph[nmax],con,idx,lowlink,in_stack;
vector <vector < long > > res;
stack < long > s;
long indl;

int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    idx.resize(n);
    lowlink.resize(n);
    in_stack.resize(n);
    idx.assign(n,-1);
    in_stack.assign(n,0);
    sol();
    return 0;
}
void read(){
    scanf("%ld %ld ",&n,&m);
    long x,y;
    while(m--){
        scanf("%ld %ld ",&x,&y);
        graph[x - 1].push_back(y - 1);
    }
}
void tarjan(long x){
    idx[x] = lowlink[x] = indl;
    indl++;
    s.push(x);
    in_stack[x] = true;
    for(vector < long > :: iterator it = graph[x].begin();it != graph[x].end();++it){
        if(idx[*it] == -1){
            tarjan(*it);
            lowlink[x] = min(lowlink[x],lowlink[*it]);
        }
        else if(in_stack[*it] == true){
            lowlink[x] = min(lowlink[x],lowlink[*it]);
        }
    }
    if(idx[x] == lowlink[x]){
        con.clear();
        long node;
        do{
            node = s.top();
            con.push_back(node);
            s.pop();
            in_stack[node] = false;
        }while(node != x);
        res.push_back(con);
    }
}
void sol(){
    for(long it = 0;it < n;++it)
        if(idx[it] == -1)tarjan(it);
    printf("%ld\n",res.size());
    for(long i = 0;i < res.size();++i){
        for(long j = 0;j < res[i].size();++j)printf("%ld ",res[i][j] + 1);
        printf("\n");
    }
}