Cod sursa(job #2437074)

Utilizator AlexNeaguAlexandru AlexNeagu Data 8 iulie 2019 12:55:49
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#define pb push_back
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector < int > result[100005], E[200005], R_E[200005];
bool visited[100005];
stack < int > List;
int n, m, x, y, cnt = 0;
void Dfs1(int node, int val)
{
    visited[node] = 0;
    result[val].pb(node);
    for (auto it : R_E[node])
        if (visited[it])
    Dfs1(it, val);
}
void Dfs(int node)
{
    visited[node] = 1;
    for (auto it : E[node])
        if (!visited[it])
        Dfs(it);
    List.push(node);
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y;
        E[x].pb(y);
        R_E[y].pb(x);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
            Dfs(i);
    }
    while (!List.empty())
    {
        int node = List.top();
        List.pop();
        if (visited[node])
        {
            cnt++;
            Dfs1(node, cnt);
        }
    }
    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++)
    {
        for (auto it : result[i])
            cout << it << " ";
        cout << "\n";
    }
    return 0;
}