Cod sursa(job #1820292)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 1 decembrie 2016 15:41:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

const int SPQR = 1e5 + 5;

vector<vector<int>> ctc;
bitset<SPQR> instk, gws;
vector<int> stk;

vector<int> g[SPQR];
int low[SPQR], lvl[SPQR];

void dfs(int nod) {
    static int now = 0;

    instk[nod] = true;
    gws[nod] = true;
    stk.push_back(nod);
    low[nod] = lvl[nod] = ++now;


    for (auto i: g[nod]) {
        if (!gws[i])
            dfs(i);
        if (instk[i])
            low[nod] = min(low[nod], low[i]); }

    if (low[nod] == lvl[nod]) {
        int tmp;

        ctc.push_back(vector<int>(0));
        do {
            tmp = stk.back();
            stk.pop_back(), instk[tmp] = false;
            ctc.back().push_back(tmp); }
        while (tmp != nod); } }

int main(void) {
    ifstream fi("ctc.in");
    ofstream fo("ctc.out");
    int n, m, u, v;

    fi >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fi >> u >> v;
        g[u].push_back(v); }

    for (int i = 1; i <= n; ++i)
        if (!gws[i])
            dfs(i);

    fo << ctc.size() << '\n';
    for (auto &i: ctc) {
        for (auto j: i)
            fo << j << ' ';
        fo << '\n'; }

    return 0; }