Cod sursa(job #1736906)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 2 august 2016 21:24:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 100000 + 1;

vector<int> G[MAX_N];
vector<int> GT[MAX_N];

vector<int> topsort;
bool visited[MAX_N];

vector<vector<int>> scc;

int N, M;

void dfs(int node)
{
    visited[node] = true;

    for (int v : G[node])
        if (!visited[v])
            dfs(v);

    topsort.push_back(node);
}

void dfsT(int node)
{
    visited[node] = false;

    for (int v : GT[node])
        if (visited[v])
            dfsT(v);

    scc.back().push_back(node);
}

void StronglyConnectedComponents()
{
    for (int i = 1; i <= N; ++i)
        if (!visited[i])
            dfs(i);

    reverse(topsort.begin(), topsort.end());

    for (int node : topsort)
    {
        if (visited[node])
        {
            scc.push_back({});
            dfsT(node);
        }
    }
}

int main()
{
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    in >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int a, b;
        in >> a >> b;

        G[a].push_back(b);
        GT[b].push_back(a);
    }

    StronglyConnectedComponents();

    out << scc.size() << "\n";

    for (auto v : scc)
    {
        for (int x : v)
            out << x << " ";

        out << "\n";
    }

    return 0;
}