Cod sursa(job #2563036)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 29 februarie 2020 21:56:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
	
#include <vector>
	
#include <stack>
	
#define N 100005
	
using namespace std;
	
ifstream in("biconex.in");
	
ofstream out("biconex.out");
	
vector<int>a[N], sol[N];
	
stack<int> st;
	
int v[N], h[N], k=0;
	
void dfs(int i, int j){
	
    int doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat;
	
    v[i]=h[i]=j;
	
    st.push(i);
	
    for(auto it:a[i]){
	
        if(!v[it]){
	
            doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat=st.size();
	
            dfs(it, j+1);
	
            v[i]=min(v[i], v[it]);
	
            if(v[it]>=j){
	
                sol[++k].push_back(i);
	
                while(st.size()!=doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat){
	
                    sol[k].push_back(st.top());
	
                    st.pop();
	
                }
	
            }
	
        }
	
        v[i]=min(v[i], h[it]);
	
    }
	
}
	
int main() { 
	
    int n,m,i,x,y;
	
    in>>n>>m;
	
    for(i=0; i<m; ++i){
	
        in>>x>>y;
	
        a[x].push_back(y);
	
        a[y].push_back(x);
	
    }
	
    dfs(1,1);
	
    out<<k<<"\n";
	
    for(i=1; i<=k; ++i){
	
        for(auto it:sol[i])
	
            out<<it<<" ";
	
        out<<"\n";
	
    }
	
    return 0;
	
}