Cod sursa(job #1479058)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 30 august 2015 14:37:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;

int n,m,idx[100010],lowlink[100010],in_stack[100010],index;
vector <int> vert[100010],ctc;
stack <int> s;

vector< vector<int> > sol;

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

void tarjan(int v)
{
    index++;
    idx[v]=index; lowlink[v]=index;
    s.push(v); in_stack[v]=1;

    //printf("%d\n",656);
    vector<int>::const_iterator it;

    for(it=vert[v].begin();it!=vert[v].end();it++)
        if(idx[*it]==0) { tarjan(*it); lowlink[v]=minim(lowlink[v],lowlink[*it]); }
        else if(in_stack[*it]) lowlink[v]=minim(lowlink[v],idx[*it]);

    if(lowlink[v]==idx[v])
    {
        ctc.clear();
        int node;
        do
        {
            ctc.push_back(node=s.top()); s.pop(); in_stack[node]=0;
        }while(node!=v);
        sol.push_back(ctc);
    }
}

int main()
{
    int n1,n2,j;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d",&n1,&n2);
        vert[n1].push_back(n2);
    }
    for(int i2=1;i2<=n;i2++)
        if(idx[i2]==0) tarjan(i2);

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