Cod sursa(job #3188634)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 ianuarie 2024 16:32:38
Problema Componente biconexe Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("biconex.in");
ofstream G("biconex.out");
vector<int> g[100001];
int n,m,i,j,t,d[100001],l[100001],c,k;
stack<pair<int,int> > s;
vector<pair<int,int> > e[100001];
void A(int i,int y)
{
	d[i]=l[i]=++t;
	int j,k=g[i].size(),r;
	for(j=0;j<k;++j) {
        if(r=g[i][j],!d[r]) {
			if(s.push({r,i}),A(r,i),l[i]=min(l[i],l[r]),l[r]>=d[i]) {
				for(;!s.empty()&&(s.top().first!=r||s.top().second!=i);e[c].push_back(s.top()),s.pop());
				e[c].push_back(s.top()),s.pop(),++c;
			}
		} else if(r!=y)
            if(l[i]=min(l[i],d[r]),d[r]<d[i])
                s.push({r,i});
	}
}
int main()
{
    for(F>>n>>m;m--;F>>i>>j,g[i].push_back(j),g[j].push_back(i));
    for(s.push({1,0}),A(1,0),G<<c<<'\n',i=0;i<c;G<<'\n',++i)
        if(k=e[i].size(),k==1)
            G<<e[i][0].first<<' '<<e[i][0].second;
        else
            for(j=0;j<k;G<<e[i][j].first<<' ',++j);
	return 0;
}