Cod sursa(job #3188658)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 ianuarie 2024 17:07:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 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],p[100001],c,k;
stack<pair<int,int> > s;
set<int> e[100001];
set<int>::iterator q;
void A(int i)
{
	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(p[r]=i,s.push({r,i}),A(r),l[i]=min(l[i],l[r]),l[r]>=d[i]) {
				for(e[c].insert(s.top().second);s.top().first!=r||s.top().second!=i;e[c].insert(s.top().first),s.pop());
				e[c].insert(s.top().first),s.pop(),++c;
			}
		} else if(r!=p[i])
            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,-1}),A(1),G<<c<<'\n',i=0;i<c;G<<'\n',++i)
        for(q=e[i].begin();q!=e[i].end();G<<*q<<' ',++q);
	return 0;
}