Cod sursa(job #3294220)

Utilizator Andrei012Trache Andrei Andrei012 Data 19 aprilie 2025 20:47:30
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("biconexe.in");
ofstream fout("biconexe.out");

vector<int> v[100001], reversed[100001],ans[100001];
stack<int> s;
int parc[100001],biconex[100001];

void dfs_normal(int node) {
    parc[node] = 1;
    for (int i=0;i<v[node].size();++i) {
        int node1 = v[node][i];
        if (parc[node1] == 0)
            dfs_normal(node1);
    }
    s.push(node);
}

void dfs(int node,int comp) {
    parc[node] = 1;
    biconex[node] = comp;
    for (int i=0;i<reversed[node].size();++i) {
        int node1 = reversed[node][i];
        if (parc[node1] == 0)
            dfs(node1,comp);
    }
}

int main() {

    int i,j,k,n,m,x,y,node,comp=0;
    fin>>n>>m;
    for (i=1;i<=m;++i) {
        fin>>x>>y;
        v[x].push_back(y);
        reversed[y].push_back(x);
    }
    for(i=1;i<=n;++i) {
        if (parc[i]==0)
            dfs_normal(i);
    }
    memset(parc,0,sizeof(parc));
    while (s.size()!=0) {
        node=s.top();
        s.pop();
        if(parc[node]==0)
            dfs(node,++comp);
    }
    for(i=1;i<=n;++i) {
        ans[biconex[i]].push_back(i);
    }
    fout<<comp<<'\n';
    for(i=1;i<=comp;++i) {
        for (j=0;j<ans[i].size();++j) {
            fout<<ans[i][j]<<" ";
        }
        fout<<'\n';
    }
    return 0;
}