Cod sursa(job #688562)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 23 februarie 2012 17:42:10
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>

using namespace std;

const int kvert = 100005;
vector<int> graph[kvert];
vector<int> stack;
vector< vector<int> > str_con;
int n, m, vis[kvert], v_index[kvert], v_lowlink[kvert], instack[kvert];

void read(){
    assert(freopen("ctc.in","r",stdin)!=NULL);
    scanf("%d%d",&n ,&m);
    int x, y;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d",&x ,&y);
        graph[x].push_back(y);
    }
}

void dfs(int x){
    vis[x] = 1;
    v_lowlink[x] = v_index[x];
    stack.push_back(x);
    instack[x] = 1;
    for(int i = 0; i < graph[x].size(); ++i){
        if(!vis[graph[x][i]]){
            v_index[graph[x][i]] = v_index[x] + 1;
            dfs(graph[x][i]);
            v_lowlink[x] = min(v_lowlink[x], v_lowlink[graph[x][i]]);
        }
        else if(instack[graph[x][i]])
            v_lowlink[x] = min(v_lowlink[x], v_lowlink[graph[x][i]]);
    }
    if(v_lowlink[x] == v_index[x]){
        vector<int> aux;
        while(stack.back() != x){
            aux.push_back(stack.back());
            instack[stack.back()] = 0;
            stack.pop_back();
        }
        aux.push_back(stack.back());
        instack[x] = 0;
        stack.pop_back();
        str_con.push_back(aux);
        aux.clear();
    }
}

void solve(){
    int i;
    for(i = 1; i <= n; ++i)
        if(!vis[i])
            dfs(i);
}

void write(){
    assert(freopen("ctc.out","w",stdout)!=NULL);
    printf("%d\n",str_con.size());
    int i, j;
    for(i = 0; i < str_con.size(); ++i){
        for(j = 0; j < str_con[i].size(); ++j)
            printf("%d ",str_con[i][j]);
        printf("\n");
    }
}

int main(){
    read();
    solve();
    write();
    return 0;
}