Cod sursa(job #1235142)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 28 septembrie 2014 20:29:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
//horatiu11
# include <cstdio>
# include <algorithm>
# include <vector>
# include <stack>
# include <bitset>
# define nmax 100001
using namespace std;
int n,m,x,y,l,sol,Ind[nmax],Min_Ind[nmax];
vector <int>G[nmax],Rez[nmax];
stack <int>st;
bitset <nmax>used;
void dfs(int x)
{
    int i,val;
    ++l;
    Ind[x]=Min_Ind[x]=l;
    st.push(x);
    used[x]=1;
    for(i=0;i<G[x].size();++i)
    {
        val=G[x][i];
        if(!Ind[val])
        {
            dfs(val);
            Min_Ind[x]=min(Min_Ind[x],Min_Ind[val]);
        }
        else if(used[val])
            Min_Ind[x]=min(Min_Ind[x],Min_Ind[val]);
    }
    if(Ind[x]==Min_Ind[x])
    {
        ++sol;
        do{
            val=st.top();st.pop();
            used[val]=0;
            Rez[sol].push_back(val);
        }while(x!=val);
    }
}
int main()
{
    int i,j;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
    }
    for(i=1;i<=n;++i)
        if(!Ind[i])
            dfs(i);
    printf("%d\n",sol);
    for(i=1;i<=sol;++i)
    {
        for(j=0;j<Rez[i].size();++j)
            printf("%d ",Rez[i][j]);
        printf("\n");
    }
    return 0;
}