Cod sursa(job #2437071)

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