Cod sursa(job #2704868)

Utilizator Snake2003lalallalal Snake2003 Data 11 februarie 2021 15:31:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define Nmax 100005

using namespace std;

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

int vf, muchii;

int x, y;

vector < int > Numbers[Nmax];

int ctc;

vector < int > Numbers_Intors[Nmax];
vector < int > CTC_URI[Nmax];

stack < int > Stiva;

int Visited[Nmax];

inline void DFS(int Nod)
{
    int Vecin;

    Visited[Nod] = 1;

    for(unsigned int i = 0; i < Numbers[Nod].size(); ++ i)
    {
        Vecin = Numbers[Nod][i];
        if(Visited[Vecin] == 0)
            DFS(Vecin);
    }
    Stiva.push(Nod);
}

inline void DFS_2(int Nod)
{
    int Vecin;

    Visited[Nod] = 2;

    CTC_URI[ctc].push_back(Nod);

    for(unsigned int i = 0; i < Numbers_Intors[Nod].size(); ++ i)
    {
        Vecin = Numbers_Intors[Nod][i];
        if(Visited[Vecin] == 1)
            DFS_2(Vecin);
    }
}

int main()
{
    fin >> vf >> muchii;
    for(int i = 1; i <= muchii; ++ i)
    {
        fin >> x >> y;

        Numbers[x].push_back(y);
        Numbers_Intors[y].push_back(x);
    }
    for(int i = 1; i <= vf; ++ i)
    {
        if(Visited[i] == 0)
            DFS(i);
    }
    while(!Stiva.empty())
    {
        int top = Stiva.top();

        if(Visited[top] == 1)
        {
            ctc ++;
            DFS_2(top);
        }
        Stiva.pop();
    }
    fout << ctc << "\n";
    for(int i = 1; i <= ctc; ++ i)
    {
        for(unsigned int j = 0; j < CTC_URI[i].size(); ++ j)
            fout << CTC_URI[i][j] << " ";
        fout << "\n";
    }
    return 0;
}