Cod sursa(job #2187277)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 26 martie 2018 12:50:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector <int> G[2][100005];
vector <int> comp[100005];
stack <int> kosaraju;
int viz[100005],m,n,cnt;
void dfs(int nod,int t)
{
    viz[nod]=1;
    for(auto fiu:G[t][nod])
    {
        if(!viz[fiu])
        {
            dfs(fiu,t);
        }
    }
    if(t==0)
        kosaraju.push(nod);
    else
        comp[cnt].push_back(nod);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    int nod1,nod2;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&nod1,&nod2);
        G[0][nod1].push_back(nod2);
        G[1][nod2].push_back(nod1);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i,0);
    memset(viz,0,sizeof(viz));
    while(!kosaraju.empty())
    {
        if(!viz[kosaraju.top()])
        {
            cnt++;
            dfs(kosaraju.top(),1);
        }
        kosaraju.pop();
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    {
        for(auto nod:comp[i])
            printf("%d ",nod);
        printf("\n");
    }
    return 0;
}