Cod sursa(job #3157389)

Utilizator BadHero112Ursu Vasile BadHero112 Data 15 octombrie 2023 14:33:53
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=200001;
using namespace std;

int n,m,t=0;
int parent[maxn],disc[maxn],low[maxn],chk[maxn];
vector<int> A[maxn];
stack<pair<int,int>> B;

void dfs(int i){
	disc[i]=t;
	low[i]=t;
	int childs=0;
	t++;
	chk[i]=1;
	for(int j=0;j<A[i].size();j++){
		if(!chk[A[i][j]]){
			childs++;
			B.push({i,A[i][j]});
			parent[A[i][j]]=i;
			dfs(A[i][j]);
			low[i]=min(low[i],low[A[i][j]]);
			if(parent[i]==-1&&A[i].size()>1){
				int sw=1;
				while(!(B.top().F==i&&B.top().S==A[i][j])){
					cout<<B.top().S+1<<" ";
					B.pop();
					sw=0;
				}
				if(sw)cout<<B.top().S+1<<" "<<B.top().F+1<<endl;
				else cout<<B.top().S+1<<endl;
				B.pop();
			}
			else if(parent[i]!=-1&&low[A[i][j]]>=disc[i]){
				int sw=1;
				while(!(B.top().F==i&&B.top().S==A[i][j])){
					cout<<B.top().S+1<<" ";
					B.pop();
					sw=0;
				}
				if(sw)cout<<B.top().S+1<<" "<<B.top().F+1<<endl;
				else cout<<B.top().S+1<<endl;
				B.pop();
			}
		}
		else if(parent[i]!=A[i][j]&&disc[A[i][j]]<low[i]){
			low[i]=disc[A[i][j]];
			B.push({i,A[i][j]});
		}
	}
}


/*void dfs2(int i){
	chk[i]=1;
	for(int j=0;j<A[i].size();j++){
		B.push_back({i,A[i][j]});
		if(!chk[A[i][j]]){
			dfs(A[i][j]);
			if(artic[i]){
				while(B.top()!={i,A[i][j]}){
					cout<<B.top().
				}
			}
		}
	}
}*/

int main(){
	ifstream cin("biconex.in");
	ofstream cout("biconex.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		A[a].push_back(b);
		A[b].push_back(a);
	}
	parent[0]=-1;
	dfs(0);
	while(B.size()){
		cout<<B.top().S+1<<" "<<B.top().F+1<<endl;
		B.pop();
	}
}