Cod sursa(job #2526745)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 19 ianuarie 2020 09:37:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;
int N, M, a, b, NrCTC;
int checked[NMAX];

stack< int > S;
vector< int >G[NMAX],     //Graful propriu-zis
           GT[NMAX],    //Transpusa grafului
           CTC[NMAX];   //Componentele tare conexe

void DFS1(int node)
{
    checked[node] = 1;

    for(size_t i = 0; i < G[node].size(); ++i) {
        int next = G[node][i];

        if(!checked[next])
            DFS1(next);
    }

    S.push(node);
}

void DFS2(int node)
{
    checked[node] = 2;
    CTC[NrCTC].push_back(node);

    for(size_t i = 0; i < GT[node].size(); ++i) {
        int next = GT[node][i];

        if(checked[next] == 1)
            DFS2(next);
    }
}

void Solution()
{
    for(int i = 1; i <= N; ++i)
        if(!checked[i])
            DFS1(i);

    while(!S.empty()) {
        int Node = S.top();

        if(checked[Node] == 1) {
            NrCTC++;
            DFS2(Node);
        }
        S.pop();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    fin >> N >> M;
    for(int i = 0; i < M; i++) {
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

    Solution();

    fout << NrCTC << "\n";
    for(int i = 1; i <= NrCTC; ++i) {
        for(size_t j = 0; j < CTC[i].size(); ++j)
            fout << CTC[i][j] << " ";

        fout << "\n";
    }
}