Cod sursa(job #1811604)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 21 noiembrie 2016 13:13:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 10;

int n, m;
bool used[nmax];
vector < int > g[nmax], gt[nmax];

int cnt;
int scc[nmax];
vector < int > s;

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);

        g[x].push_back(y);
        gt[y].push_back(x);
    }
}

void dfs(int node) {
    used[node] = 1;
    for (auto &it : g[node]) {
        if (used[it]) continue;
        dfs(it);
    }

    s.push_back(node);
}

void dfsT(int node) {
    scc[node] = cnt;
    for (auto &it : gt[node]) {
        if (scc[it]) continue;
        dfsT(it);
    }
}

void solve() {
    ///build stack
    for (int i = 1; i <= n; ++i)
        if (!used[i]) dfs(i);

    for (auto it = s.rbegin(); it != s.rend(); ++it)
        if (!scc[*it]) cnt++, dfsT(*it);
}

void output() {
    vector < int > ans[cnt+1];
    for (int i = 1; i <= n; ++i)
        ans[scc[i]].push_back(i);

    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i, printf("\n"))
        for (auto &it : ans[i]) printf("%d ", it);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    input();
    solve();
    output();

    return 0;
}