Cod sursa(job #3187110)

Utilizator sugpula12345pula pizda sugpula12345 Data 27 decembrie 2023 16:17:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector<int>V[100002];
vector<int>Vt[100002];
vector<int> Componente[100002];
stack<int>S;
int n,m,ctc,v[100002];

void dfs(int k){
    v[k]=1;
    
    for(auto vec:V[k])
        if(!v[vec]) dfs(vec);
    S.push(k);
}

void dfs2(int k){
    v[k]=2;
    Componente[ctc].push_back(k);
    
    for(auto vec:Vt[k])
        if(v[vec]==1) dfs2(vec);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int a,b;
        cin>>a>>b;
        V[a].push_back(b);
        Vt[b].push_back(a);
    }
    //topo sort
    for(int i=1;i<=n;++i)
        if(!v[i]) dfs(i);
        
    while(!S.empty()){
        int nod=S.top();
        S.pop();
        
        if(v[nod]==1){
            ctc++;
            dfs2(nod);
        }
    }
    
    cout<<ctc<<'\n';
    for(int i=1;i<=ctc;++i,cout<<'\n')
        for(int j=0;j<Componente[i].size();++j) cout<<Componente[i][j]<<" ";
    return 0;
}