Cod sursa(job #1150240)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 22 martie 2014 18:38:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100009
using namespace std;
struct vecini
{
    vector<int> v;
};
vecini g[nmax],rasp[nmax];
int lowlink[nmax];
int index[nmax],curent=0,nr=0;
stack<int> st;bool stiva[nmax];
void tarjan(int x)
{
    curent++;
    index[x]=curent;
    lowlink[x]=curent;
    st.push(x);
    stiva[x]=true;
    int lung=g[x].v.size(),i,y;
    for(i=0;i<lung;++i)
    {
        y=g[x].v[i];
        if(index[y]==0)
        {
            tarjan(y);
            lowlink[x]=min(lowlink[x],lowlink[y]);
        }
        else
        {
            if(stiva[y]==true)
                lowlink[x]=min(lowlink[x],index[y]);
        }
    }
    if(index[x]==lowlink[x])
    {
        nr++;
        y=st.top();
        do
        {
            y=st.top();
            rasp[nr].v.push_back(y);
            st.pop();
            stiva[y]=false;
        }
        while(x!=y);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,i,j,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        g[x].v.push_back(y);
    }
    for(i=1;i<=n;i++)
        if(index[i]==0)
        {
            tarjan(i);
        }
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
    {
        for(j=0;j<rasp[i].v.size();++j)
            printf("%d ",rasp[i].v[j]);
        printf("\n");
    }

    return 0;
}