Cod sursa(job #2546588)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 14 februarie 2020 11:59:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;
vector<int>v[100005];
vector<int>g[100005];
int cnt,fr[100005],st[100005];
void dfs(int nod)
{
    fr[nod]=1;
    vector<int>::iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        int l=*it;
        if(fr[l])continue;
        dfs(l);
    }
    st[cnt--]=nod;
}
vector<int>sol[100005];
int dfs1(int nod)
{
    fr[nod]=1;
    vector<int>::iterator it;
    for(it=g[nod].begin();it!=g[nod].end();it++)
    {
        int l=*it;
        if(fr[l])continue;
        dfs1(l);
    }
    sol[cnt].push_back(nod);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    cnt=n;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        ++a;
        ++b;
        v[a].push_back(b);
        g[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        if(!fr[i])dfs(i);
    fill(fr+1,fr+n+1,0);
    cnt=0;
    for(i=1;i<=n;i++)
    {
      if(!fr[st[i]])cnt++,dfs1(st[i]);
    }
    cout<<cnt<<"\n";
    for(i=1;i<=cnt;i++)
    {
        vector<int>::iterator it;
        for(it=sol[i].begin();it!=sol[i].end();it++)
            cout<<*it<<" ";
        cout<<"\n";
    }
    return 0;
}