Cod sursa(job #3235774)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 21 iunie 2024 14:28:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
//solutie tarjan scrisa de Rares Feraru

#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;
const int MMAX = 2e5;

vector<int> adj[NMAX+1];

int idx[NMAX+1], linked[NMAX+1];

bool marked[NMAX+1];

stack<int> stiva;

int cnt;

vector<vector<int>> rez;

void tarjan(int nod){
    
    cnt ++;
    
    
    linked[nod] = cnt;
    idx[nod] = cnt;
    
    stiva.push(nod);
    
    marked[nod] = true;
    
    for(int next : adj[nod]){
        
        if(idx[next] == -1){
            
            tarjan(next);
            linked[nod] = min(linked[nod], linked[next]);
            
        }else if(marked[next]){
            
            linked[nod] = min(linked[nod], linked[next]);
            
        }
        
    }
    
    
    if(idx[nod] == linked[nod]){
        
       
        
        vector<int> aux;
        
        while(!stiva.empty() and stiva.top() != nod){
            
            aux.push_back(stiva.top());
            marked[stiva.top()] = false;
            
            stiva.pop();
            
        }
        
        aux.push_back(nod);
        marked[nod] = false;
        
        rez.push_back(aux);
        
        stiva.pop();
        
    }
    
}

int main()
{
    int n, m;
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y;
        f >> x >> y;
        
        adj[x].push_back(y);
        
    }
    
    for(int i=1; i<=n; i++)
        idx[i] = -1;
        
    for(int i=1; i<=n; i++)
        if(idx[i] == -1){
                
            tarjan(i);  
            
        }
        
    
    g << rez.size() << "\n";
    
    for(int i=0; i<rez.size(); i++){
        
        for(int j=0; j<rez[i].size(); j++)
            g << rez[i][j] << ' ';
            
        g << "\n";
    }

    return 0;
}