Cod sursa(job #899575)

Utilizator ZanarokStefan Mocanu Zanarok Data 28 februarie 2013 15:14:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <stack>
#define MAX 100005

using namespace std;




vector <int> adj[MAX],idx,lowlink,in_stack,con;
vector <vector <int> > C;
stack <int> S;

int n, m,indecs;

int minim (int a, int b)
{
    if(a<b)
        return a;
    return b;
}
void tarjan(int a)
{
    idx[a]=indecs;
    lowlink[a]=indecs;
    S.push(a);
    in_stack[a]=1;
    indecs++;
    //
    for(int k=0;k<adj[a].size();k++)
        if(idx[adj[a][k]]==-1)
        {
            tarjan(adj[a][k]);
            lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
        }
        else
            if(in_stack[adj[a][k]])
                lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
        if(idx[a]==lowlink[a])
        {
            con.clear();
            int node;
            do
            {
                node=S.top();
                con.push_back(node);
                S.pop();
                in_stack[node]=0;
            }while(node!=a);
            C.push_back(con);
        }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y;
    for(int k=1;k<=m;k++)
    {
        scanf("%d %d",&x,&y);
        adj[x-1].push_back(y-1);
    }
    idx.resize(n), lowlink.resize(n), in_stack.resize(n);
    idx.assign(n, -1), in_stack.assign(n, 0);
    for(int k=0;k<n;k++)
        if(idx[k]==-1)
            tarjan(k);
    printf("%d\n",C.size());
    for(int k=0;k<=C.size()-1;k++)
    {
        for(int j=0;j<=C[k].size()-1;j++)
            printf("%d ",C[k][j]+1);
        printf("\n");
    }
    return 0;
}