Cod sursa(job #2748988)

Utilizator paisieRusu Paisie paisie Data 4 mai 2021 14:55:19
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define forr(X) for(int i = 0; i<X; i++)
#pragma GCC optimize("Ofast")

int n, m;
vector <int> a[100005];
int vis[100005], l[100005], de[100005],  last = 1, d=1, cnt =0;
vector <int> point;
vector <int>ans[100005];

int dfs(int x, int previ){
	if(!vis[x]){ 
		//cout<<"un: "<<x<<endl;
		vis[x] = 1;
		de[x] = d;
		l[x] = d;
		point.push_back(x);
		for(auto it: a[x]){
			if(it != previ){
				//previ = x;
				d++;
				dfs(it, x);
			}
			
		}
	}
	else{
		if(de[x]<de[previ]){
			d--;
			//cout<<"vis: "<<x<<endl;

			for(auto it : point){
				l[it] = de[x];
			}
			last = previ+1;
			point.clear();
		}
		
	}

}

int dfs2(int x, int previ){
	if(x ==1){
		//code for head wt 2+ children
	}
	if(!vis[x]){
		vis[x] =1;
		ans[cnt].push_back(x);
		if(l[x]>=de[previ] && x!=1){
			//cout<<" x= "<<x<<endl;
			cnt++;
		}
		for(auto it: a[x]){
			if(it != previ){
				//previ = x;
				d++;
				dfs2(it, x);
			}
			
		}
		
	}
}

int main(){
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	cin>>n>>m;
	int x, y;
	for(int i = 1; i <= m; i++){
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 1);
	//forr(n+1)cout<<l[i]<<" ";
	//cout<<endl;
	//forr(n+1)cout<<de[i]<<" ";
	
	memset(vis, 0, sizeof(int) * 100005);
	point.clear();
	
	
	dfs2(1, 1);
	
	cout<<cnt;
	for(int i =0; i<cnt; i++){
		for(auto it : ans[i]){
			//cout<<it<<" ";
		}
		//cout<<endl;
	}

}