Cod sursa(job #2928607)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 23 octombrie 2022 14:54:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int nmax = 100005;

int n, m, x, y, tmp, ans;

vector<int> G[nmax];
vector<vector<int>> sol;
stack<int> Q;

int low[nmax], dt[nmax];
bool viz[nmax], smb[nmax];

void DFS(int node){
    
    viz[node] = 1;
    low[node] = dt[node] = tmp++;
    Q.push(node);
    smb[node] = 1;

    for(auto x:G[node]){
        
        if(!viz[x]){
            
            DFS(x);
            low[node] = min(low[node], low[x]);
        }
        else if(smb[x])
            low[node] = min(low[node], low[x]);
            
    }

    if(low[node] == dt[node]){
        
        vector<int> a;
        
        ans++;
        
        while(!Q.empty() && Q.top() != node){
            
            a.push_back(Q.top());
            smb[Q.top()] = 0;
            Q.pop();

            //cout<<w<<" ";
        }
        
        a.push_back(Q.top());
        smb[Q.top()] = 0;
        Q.pop();
        
        //cout<<w<<"\n";
        
        sol.push_back(a);

    }
}

int main(){
    
    f >> n >> m;
    
    for(int i = 1; i <= m; ++i){
        
        f >> x >> y;
        G[x].push_back(y);
    }

    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            DFS(i);

    g << ans << "\n";
    
    for(int i = 0; i < ans; ++i){
        for(auto bt:sol[i])
            g << bt << ' ';
        
        g << "\n";
    }
    
    return 0;
}