Cod sursa(job #3235895)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 23 iunie 2024 21:37:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
//solutie scrisa de Rares Feraru

#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;

vector<int> adj[NMAX+1], adj2[NMAX+1];
vector<int> rez[NMAX+1];

int inv[NMAX+1];
int invers, cnt;

bool marked[NMAX+1];

void dfs(int nod, bool scnd){
    
    if(scnd == true)
        rez[cnt].push_back(nod);
    
    marked[nod] = true;
    
    if(scnd == false){
        
        for(int next : adj[nod])
            if(!marked[next])
                dfs(next, scnd);
        
        invers -= 1;
        inv[invers] = nod;
        
        
    }else{
        
        for(int next : adj2[nod])
            if(!marked[next])
                dfs(next, scnd);
        
    }
    
    
}

int main()
{
    
    int n, m;
    f >> n >> m;
    
    invers = n + 1;
    
    //formam listele de adiacenta
    
    for(int i=1; i<=m; i++){
        
        int x, y;
        f >> x >> y;
        
        adj[x].push_back(y);
        adj2[y].push_back(x);
        
    }
    
    //formam lista inversa de parcurgere a componentelor conexe
    
    for(int i=1; i<=n; i++)
        if(!marked[i])
            dfs(i, 0);
        
            
    for(int i=1; i<=n; i++)
        marked[i] = false;
 
    //formam elementele tare conexe si le grupam
    
    for(int i=1; i<=n; i++)
        if(!marked[inv[i]])
            cnt ++, dfs(inv[i], 1);
            
    g << cnt << "\n";
    
    for(int i=1; i<=cnt; i++){
        
        for(int j=0; j<rez[i].size(); j++)
            g << rez[i][j] << ' ';
            
        g << "\n";
        
    }

    return 0;
}