Cod sursa(job #1930231)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 18 martie 2017 17:14:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define z(x) (x & (-x))

typedef long long ll;

using namespace std;

int n, m, x, y, v;

vector < int > V[200100], I[200100], T[200100];
bool viz[200100];
int rs[200100], cnt;
stack < int > St;
void dfs(int x)
{
    viz[x] = 1;
    for (auto it : V[x])
        if (!viz[it]) dfs(it);
    St.push(x);
}

void dfs2(int x)
{
    rs[x] = cnt;
    for (auto it : I[x])
        if (rs[it] == -1) dfs2(it);
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> x >> y, V[x].push_back(y), I[y].push_back(x), rs[i] = -1;
    for (int i = 1; i <= n; i++)
        if (!viz[i]) dfs(i);
    while (St.size())
    {
        int curr = St.top();
        if (rs[curr] == -1)
        {
            cnt++;
            dfs2(curr);
        }
        St.pop();
    }
    for (int i = 1; i <= n; i++)
        T[rs[i]].push_back(i);
    cout << cnt << "\n";
    for (auto it : T)
    {
        for (auto it2 : it)
            cout << it2 << " ";
        cout << (it.empty() ? "" : "\n");
    }
    return 0;
}