Cod sursa(job #2207220)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 25 mai 2018 11:02:21
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");


const int NMax = 100010;
vector<vector<int> > ans;
int d[NMax];
int st[NMax];
int onstack[NMax];
int ctc[NMax];
int k;
vector<int> G[NMax];
int nr = 1;
int n, m, x, y;

int dfs(int node, int depth){
    d[node] = depth;
    st[++k] = node;
    onstack[node] = true;

    for(int i = 0; i < G[node].size();i++){
        int next = G[node][i];
        if(ctc[next]) continue;
        if(!onstack[next]) d[node] = min(d[node], dfs(next, depth + 1));
        else d[node] = min(d[node], d[next]);
    }

    if(d[node] == depth){
        ans.push_back(vector<int>());

        while(st[k] != node){
            ans[ans.size() - 1].push_back(st[k]);
            onstack[st[k]] = false;
            ctc[st[k--]] = nr;
        }
        onstack[st[k]] = false;
        ans[ans.size() - 1].push_back(st[k]);
        ctc[st[k--]] = nr;

        nr++;
    }

    return d[node];
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> x >> y;

        G[x].push_back(y);
    }

    for(int i = 1; i <= n; i++){
        if(ctc[i] == 0){
            dfs(i, 1);
        }
    }

    fout << ans.size()<< '\n';

    for(int i = 0; i < ans.size(); i++){
        for(int j = 0; j < ans[i].size(); j++){
            fout << ans[i][j] << ' ';
        }

        fout << '\n';
    }

    return 0;
}