Cod sursa(job #2209299)

Utilizator jurjstyleJurj Andrei jurjstyle Data 2 iunie 2018 17:31:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <list>
 
using namespace std;
 
ifstream f("ctc.in");
ofstream g("ctc.out");
 
const int NMAX = 100002;
 
int N, M;
vector <int> G[NMAX];
stack <int> St;
vector <bool> Viz;
vector <int> Nivel, Length, Comp_curent;
vector <vector <int>> Cc;
int nv;
 
void DFS(int);
 
int main()
{
    f >> N >> M;
    Viz = vector <bool> (N + 1, 0);
    Nivel = Length = vector <int> (N + 1, 0);
    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
    }
 
    for (int i = 1; i <= N; ++i)
        if (Nivel[i] == 0)
            DFS(i);
    g << Cc.size() << "\n";
    for (int i = 0; i < Cc.size(); ++i)
    {
        for (const int & j : Cc[i])
            g << j << " ";
        g << "\n";
    }
    f.close();
    g.close();
    return 0;
}
 
 
void DFS(int x)
{
    Viz[x] = true;
    St.push(x);
    Nivel[x] = Length[x] = ++nv;
    for (const int & y : G[x])
        if (Viz[y] == false) //daca e muchie de arbore
        {
            DFS(y);
            Length[x] = min(Length[x], Length[y]);
        }
        else //daca e muchie de intoarcere
            Length[x] = min(Length[x], Nivel[y]);
    if (Nivel[x] == Length[x])
    {
        Comp_curent.clear();
        while (true)
        {
            int nod_curent = St.top();
            Comp_curent.push_back(nod_curent);
            Viz[nod_curent] = false;
            St.pop();
            if (x == nod_curent)
                break;
        }
        Cc.push_back(Comp_curent);
    }
}