Cod sursa(job #2698878)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 23 ianuarie 2021 11:02:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

struct Edge{
	int a, b;
	int ott(int x){
		if(x==a)return b;
		else if(x==b)return a;
		else return 0;
	}
};
bool eq(const Edge &lhs, const Edge &rhs){
	return lhs.a==rhs.a && lhs.b==rhs.b;
}

const int N = 100041;
const int M = 200041;

int n, m;
vector<int> gra[N];
Edge edg[M];

bool vi[M];

int depth[N];
int lowling[N];
stack<Edge> stak;
set<int> se;

vector<vector<int>> ans;

void dfs(int a){
	lowling[a] = depth[a];
	for(auto e : gra[a]){
		auto &ed = edg[e];
		int b = ed.ott(a);
		if(!vi[e] && depth[b] == 0){ // Forward edge
			stak.push(ed);
			vi[e] = true;
			depth[b] = depth[a] + 1;
			dfs(b);
			lowling[a] = min(lowling[a], lowling[b]);
			
			if(lowling[b] >= depth[a]){
				while(!stak.empty() && !eq(stak.top(), ed)){
					se.insert(stak.top().a);
					se.insert(stak.top().b);
					stak.pop();
				}
				se.insert(stak.top().a);
				se.insert(stak.top().b);
				stak.pop();
				
				ans.push_back({});
				auto &v = ans.back();
				for(auto a : se){
					v.push_back(a);
				}
				se.clear();
			}
			
		}else{ // Backward edge
			lowling[a] = min(lowling[a], depth[b]);
		}
	}
	
	// cout << a << " " << depth[a] << " " << lowling[a] << "\n";
}

int main(){
	// ios_base::sync_with_stdio(false);
	fin >> n >> m;
	
	for(int i = 1; i <= m; ++i){
		int a, b;
		fin >> a >> b;
		edg[i] = {a,b};
		gra[a].push_back(i);
		gra[b].push_back(i);
	}
	
	depth[1] = 1;
	dfs(1);
	
	fout << ans.size() << "\n";
	for(auto &v : ans){
		for(auto a : v){
			fout << a << " ";
		}
		fout << "\n";;
	}
	
	return 0;
}