Cod sursa(job #2198708)

Utilizator PredaBossPreda Andrei PredaBoss Data 25 aprilie 2018 09:35:42
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
int n,m,x,y,howmany;
vector<int>nod[100005],ans,component[100005];
bitset<100005>ap;
int val[100005];
void go_visit(int pos)
{
    val[pos]=++howmany;
    ap[pos]=1;
    for(int i=0;i<nod[pos].size();i++)
    {
        if(ap[nod[pos][i]])
            val[pos]=min(val[pos],val[nod[pos][i]]);
        else
        {
            go_visit(nod[pos][i]);
            val[pos]=min(val[pos],val[nod[pos][i]]);
        }
    }
}
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++)
        go_visit(i);
    for(int i=1;i<=n;i++)
        ap[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(ap[val[i]]==0)
        {
            ap[val[i]]=1;
            ans.push_back(val[i]);
        }
        component[val[i]].push_back(i);
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<component[ans[i]].size();j++)
            printf("%d ",component[ans[i]][j]);
        printf("\n");
    }
    return 0;
}