Cod sursa(job #1607580)

Utilizator zertixMaradin Octavian zertix Data 21 februarie 2016 13:47:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int >g[100005],ord,com[100005],gb[100005];
int nrcom,n,m,viz[100005],asig[100005];

void citire()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int nod1,nod2;
        scanf("%d%d",&nod1,&nod2);
        g[nod1].push_back(nod2);
        gb[nod2].push_back(nod1);
    }
}
void dfs(int nod)
{
    viz[nod]=1;
    for (vector <int > :: iterator it=g[nod].begin();it!=g[nod].end();++it)
        if (!viz[*it])
            dfs(*it);
    ord.push_back(nod);
}
void assig(int nod)
{
    com[nrcom].push_back(nod);
    asig[nod]=1;
    for (vector <int > :: iterator it=gb[nod].begin();it!=gb[nod].end();++it)
        if (!asig[*it])
            assig(*it);
}
void kosaraju()
{
    for (int i=1;i<=n;++i)
        if (!viz[i])
            dfs(i);
    while (!ord.empty())
    {
        if (!asig[ord.back()])
        {
            assig(ord.back());
            ++nrcom;
        }
        ord.pop_back();
    }
    printf("%d\n",nrcom);
    for (int i=0;i<nrcom;++i)
    {
        for (vector <int > :: iterator it=com[i].begin();it!=com[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    kosaraju();
    return 0;
}