Cod sursa(job #1219865)

Utilizator tudi98Cozma Tudor tudi98 Data 15 august 2014 15:10:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define dim 100005

bool in_stack[dim];
stack  <int> S;
vector <int> v[dim];
vector < vector <int> > SCC;
int lowlink[dim],idx[dim];
int curIdx = 0;

inline int min(int a,int b){
    return (a>b?b:a);
}

void tarjan(int node){

    lowlink[node] = idx[node] = ++curIdx;
    S.push(node);
    in_stack[node] = true;
    for(int i = 0; i < v[node].size(); i++){
        if(idx[v[node][i]] == 0){
            tarjan(v[node][i]);
            lowlink[node] = min(lowlink[v[node][i]],lowlink[node]);
        }
        else if(in_stack[v[node][i]]){
            lowlink[node] = min(lowlink[v[node][i]],lowlink[node]);
        }
    }
    if(lowlink[node] == idx[node]){
        int u;
        vector<int> SCC_node;
        do{
            u = S.top();
            S.pop();
            in_stack[u] = false;
            SCC_node.push_back(u);
        } while(u != node);
        SCC.push_back(SCC_node);
    }
}



int main(){

    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    int n,m;
    scanf("%d %d\n",&n,&m);
    for(int i = 1; i <= m; i++){
        int a,b;
        scanf("%d %d\n",&a,&b);
        v[a].push_back(b);
    }

    for(int i = 1; i <= n; i++){
        if(idx[i] == 0)
            tarjan(i);
    }

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