Cod sursa(job #2200142)

Utilizator PredaBossPreda Andrei PredaBoss Data 30 aprilie 2018 14:21:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;
int n,m,x,y,howmany;
vector<int>nod[100005];
bitset<100005>ap,stk;
stack<int>s;
vector<vector<int> >ans;
int val[100005];
void go_visit(int pos)
{
    if(val[pos]==0)
    val[pos]=++howmany;
    int cop=val[pos];
    ap[pos]=1;
    stk[pos]=1;
    s.push(pos);
    for(int i=0;i<nod[pos].size();i++)
    {
        if(ap[nod[pos][i]])
        {
            if(stk[nod[pos][i]]==1)
            val[pos]=min(val[pos],val[nod[pos][i]]);
        }
        else
        {
            go_visit(nod[pos][i]);
            val[pos]=min(val[pos],val[nod[pos][i]]);
        }
    }
    if(cop==val[pos])
    {
        vector<int>which;
        int nod=0;
        while(nod!=pos)
        {
            which.push_back(s.top());
            nod=s.top();
            stk[nod]=0;
            s.pop();
        }
        ans.push_back(which);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d\n",&x,&y);
        nod[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(ap[i])
            continue;
        go_visit(i);
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}