Cod sursa(job #769947)

Utilizator cippyApetrei Ciprian cippy Data 21 iulie 2012 13:52:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<iostream>
#include<stdio.h>
#include<stack>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
#define max 100005
#define Min(a, b)  ((a) < (b) ? (a) : (b))

vector <int> adj[max],con,id,lowlink,in_stack;
vector < vector<int> > G;
stack <int>S;
int index,n;
void citire();
void afisare();
void tarjan(int);

int main()
{
    citire();
    id.resize(n),lowlink.resize(n),in_stack.resize(n);
    id.assign(n,-1),in_stack.assign(n,0);
    for(int i=0;i<n;++i)
        if(id[i] == -1)
            tarjan(i);
    afisare();
    return 0;
}



void citire()
{
        freopen("ctc.in","r",stdin);
        int nr,x,y;
        scanf("%d",&n);
        for(scanf("%d",&nr);nr > 0; --nr)
            scanf("%d%d",&x,&y),
                adj[x-1].push_back(y-1);
}
void afisare()
{
    freopen("ctc.out","w",stdout);
    printf("%d\n",int(G.size()));
    for(unsigned int i=0;i<G.size();++i){
        for(unsigned int j=0;j<G[i].size();++j)
            printf("%d ",int(G[i][j])+1);
        printf("\n");
    }
}


void tarjan(int i)
{
    id[i]=lowlink[i]=index;
    ++index;
    S.push(i),in_stack[i]=1;
    vector <int>::const_iterator it;
    for(it = adj[i].begin();it != adj[i].end(); ++it)
    {
        if(id[*it] == -1)
            tarjan(*it),
                lowlink[i]=Min(lowlink[i],lowlink[*it]);
        else if(in_stack[*it])
                lowlink[i]=Min(lowlink[i],lowlink[*it]);
    }
    if(id[i]==lowlink[i])
    {
        con.clear();
        int nod;
        do {
            con.push_back(nod = S.top());
            S.pop(),in_stack[nod]=0;
        }while(nod!=i);
        G.push_back(con);
    }
}