Cod sursa(job #2298468)

Utilizator HoratioHoratiu Duma Horatio Data 8 decembrie 2018 10:47:30
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <bits/stdc++.h>

using namespace std;

int n;
int m;

vector<int> nod[100005];
vector<int> rnod[100005];
vector<int> conex[100005];

int viz[100005];
int viz2[100005];

deque<int> coada;

void citire()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        nod[a].push_back(b);
        rnod[b].push_back(a);
    }
}

void DFSN(int i)
{
    viz[i]=1;
    coada.push_back(i);
    for(auto it:nod[i])
    {
        if(viz[it]==0)
            DFSN(it);
    }
}

void DFSR(int i,int k)
{
    viz2[i]=1;
    conex[k].push_back(i);
    for(auto it:rnod[i])
    {
        if(viz2[it]==0)
            DFSR(it,k);
    }

}


void parcurgere1()
{
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            DFSN(i);
}

int k=0;

void parcurgere2()
{
    for(auto it:coada)
    {
        if(viz2[it]==0)
        {
        DFSR(it,k);
        k++; // aceasta instructiune
        }
    }
}

void afisare()
{
    //for(auto it:coada)
        //printf("%d ",it);
    printf("%d\n",k);
    for(int i=0;i<k;i++)
    {
    for(auto it:conex[i])
        printf("%d ",it);
    printf("\n");
    }

}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    parcurgere1();
    parcurgere2();
    afisare();

    return 0;
}