Cod sursa(job #3198830)

Utilizator cacamaca12aasdga cacamaca12 Data 30 ianuarie 2024 17:51:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <stack>
#define dim 100002
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

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

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

void dfs1(int nod){
    v[nod]=2;
    Componente[ctc].push_back(nod);
    
    for(int vec:Vt[nod]) if(v[vec]==1) dfs1(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);
    }
    
    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++;
            dfs1(nod);
        }
    }
    cout<<ctc<<'\n';
    for(int i=1;i<=ctc;++i){
        for(auto x:Componente[i]) cout<<x<<" ";
        cout<<'\n';
    }
    return 0;
}