Cod sursa(job #2263793)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 19 octombrie 2018 11:44:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 100001
#define pb push_back
#define mp make_pair

vector <int> v[NMAX],sol[2*NMAX];
vector < pair < int , int > > st;
int viz[NMAX],l[NMAX],dfn[NMAX],nrc;

inline void bc(int x, int y)
{
	nrc++;
	int a,b;
	do {
		a=st.back().first;
		b=st.back().second;
		st.pop_back();
		sol[nrc].pb(a);
		sol[nrc].pb(b);
	}
	while(x!=a || y!=b);
}

inline void dfs(int nod, int tata, int niv)
{
	viz[nod]=1;
	l[nod]=niv;
	dfn[nod]=niv;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++) {
		if(*it==tata)
			continue;
		if(viz[*it]==0) {
			st.pb(mp(nod,*it));
			dfs(*it,nod,niv+1);
			l[nod]=min(l[nod],l[*it]);
			if(l[*it]>=niv)
				bc(nod,*it);
		}
		else l[nod]=min(l[nod],dfn[*it]);
	}
}

int main ()
{
	int n,m,x,y,i,j;
	ifstream f("biconex.in");
	ofstream g("biconex.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	f.close();
	dfs(1,0,0);
	g<<nrc<<'\n';
	for(i=1;i<=nrc;i++) {
		sort(sol[i].begin(),sol[i].end());
		n=sol[i].size()-1;
		g<<sol[i][0]<<" ";
		for(j=1;j<=n;j++)
			if(sol[i][j]!=sol[i][j-1])
				g<<sol[i][j]<<" ";
		g<<'\n';
	}
	g.close();
	return 0;
}