Cod sursa(job #868282)

Utilizator octavdOctavian Dumitrascu octavd Data 30 ianuarie 2013 21:22:02
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include<algorithm>
#include<iterator>
#include<stack>
#include<vector>

using namespace std ;

vector <int> list[100003],a ; //listele de adiacenta
stack <int> s; //stiva din algoritm
vector <vector < int> > ctc;  //vector de vectori de componete tare conexe

int ind,n,m,x,y,index[100003],lowlink[100003],in_stiva[10003];

int min(int a,int b)
{
	if (a<=b) return a;
	else return b;
}

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

void tarjan( int v  )
{
    index[v]= ind ;
    lowlink[v]= ind ;
    ind++;
    s.push(v) ;
    in_stiva[v]= 1;
    vector < int >::const_iterator it ;
    for(it=list[v].begin();it<list[v].end();it++)
    {
        if (index[*it]==0)
        {
            tarjan(*it);
            lowlink[v]=min(lowlink[v],lowlink [*it]);
        }
        else
            if (in_stiva[*it]!=0) lowlink[v]=min(lowlink[v],index[*it]);
    }
    if( lowlink[v]==index[v])
    {
        int aux ;
        a.clear();
        do
        {
            a.push_back(aux=s.top());
            in_stiva[aux]=0;
            s.pop();
        }
        while(v!=aux);
        ctc.push_back(a);
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        list[x].push_back(y);
    }
    ind=0;
    for(int i=1;i<=n;i++)
        if(index[i]==0)tarjan(i);
    afisare(ctc);
    return 0;
}