Cod sursa(job #1491528)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 25 septembrie 2015 17:00:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <vector>
#include <stack>
#include <cstdio>
#define min(a,b) ( (a)<(b)? (a) : (b) )
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;
    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],lowlink[*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;
}