Cod sursa(job #2527632)

Utilizator pitzurcaTudor M pitzurca Data 20 ianuarie 2020 18:37:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

int const NLIMIT = 100005;

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

int N, M, CTC;

vector <int> Edges[NLIMIT];
vector <int> Edges_T[NLIMIT];
vector <int> Result[NLIMIT];

stack <int> S;

int Visited[NLIMIT];

void read()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i ++)
    {
        int X, Y;
        fin >> X >> Y;
        Edges[X].push_back(Y);
        Edges_T[Y].push_back(X);
    }
}

void DFS(int Node)
{
    Visited[Node] = 1;
    for (int i = 0; i < Edges[Node].size(); i ++)
    {
        int Next = Edges[Node][i];
        if (!Visited[Next])
            DFS(Next);
    }

    S.push(Node);
}

void DFS_T(int Node)
{
    Visited[Node] = 2;
    Result[CTC].push_back(Node);
    for (int i = 0; i < Edges_T[Node].size(); i ++)
    {
        int Next = Edges_T[Node][i];
        if (Visited[Next] == 1)
            DFS_T(Next);
    }
}

void solve()
{
    for (int i = 1; i <= N; i ++)
        if (!Visited[i])
            DFS(i);

    while (!S.empty()) {
        int V = S.top();
        if (Visited[V] == 1) {
            DFS_T(V);
            CTC ++;
        }
        S.pop();
    }
}

void write()
{
    fout << CTC << "\n";

    for (int i = 0; i < CTC; i ++) {
        for (int j = 0; j < Result[i].size(); j ++)
            fout << Result[i][j] << " ";

        fout << "\n";
    }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}