Cod sursa(job #2420568)

Utilizator ela_topaTopa Elena ela_topa Data 12 mai 2019 17:21:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

constexpr int NX = 100010;
int N, M;
int viz[NX];
stack <int> S;
vector <int> V[NX], W[NX], CTC[NX];

void dfs(int nod)
{
    viz[nod]=1;
    for(int i=0; i<V[nod].size(); ++i)
        if(viz[V[nod][i]]==0)
            dfs(V[nod][i]);

    S.push(nod);
}

void dfs2(int nod, int nrc)
{
    viz[nod]=2;
    CTC[nrc].push_back(nod);
    for(int i=0; i<W[nod].size(); ++i)
    {
        if(viz[W[nod][i]]==1)
            dfs2(W[nod][i], nrc);
    }
}
int main()
{
    fin>>N>>M; //citesc nr de noduri si muchiile
    int x, y;
    for(int i=1; i<=M; ++i)
    {
        fin>>x>>y;
        V[x].push_back(y); //le bag in lista de vecini
        W[y].push_back(x); //si in transpusa lor
    }

    for(int i=1; i<=N; ++i)
    {
        if(viz[i]==0)
        {
            dfs(i);  //fac un dfs din fiecare nod nevizitat si le bag in stiva la intoarcere
        }
    }

    int nrc=0;
    while(!S.empty())
    {
        int nod=S.top();
        S.pop();
        if(viz[nod]==1)
        {
            nrc++; //cresc componenta
            dfs2(nod, nrc); //mai fac un dfs pe transpusa si la fiecare apel creste componenta
        }
    }

    fout<<nrc<<"\n"; //afisez
    for(int i=1; i<=nrc; ++i)
    {
        for(int j=0; j<CTC[i].size(); ++j)
            fout<<  CTC[i][j] <<" ";
        fout<<"\n";
    }
    return 0;
}