Pagini recente » Cod sursa (job #532838) | Cod sursa (job #1077091) | Cod sursa (job #21733) | Cod sursa (job #1252986) | Cod sursa (job #716930)
Cod sursa(job #716930)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#define MAXN 100010
#define mp make_pair
#define f first
#define s second
using namespace std;
stack<pair<int,int> >S;
vector<int>v[MAXN],sol[MAXN];
int viz[MAXN],n,m,comp,sus[MAXN],j;
void dfs(int x)
{
for(int i=0;i<v[x].size();i++)
if(!viz[v[x][i]])
{
viz[v[x][i]]=viz[x]+1;
S.push(mp(x,v[x][i]));
dfs(v[x][i]);
if(sus[v[x][i]]<sus[x]) sus[x]=sus[v[x][i]];
if(sus[v[x][i]]>=viz[x]) //gasit
{
comp++;
while(S.top().f!=x or S.top().s!=v[x][i])
{
sol[comp].push_back(S.top().s);
S.pop();
}
S.pop();
sol[comp].push_back(x);
sol[comp].push_back(v[x][i]);
}
} else if(viz[v[x][i]]<sus[x]) sus[x]=viz[v[x][i]];
}
int main()
{
int i,x,y;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
viz[1]=1;
for(i=1;i<=n;i++) sus[i]=int(2e9);
dfs(1);
fo<<comp<<"\n";
for(i=1;i<=comp;i++)
{
sort(sol[i].begin(),sol[i].end());
for(j=0;j<sol[i].size();j++) fo<<sol[i][j]<<" ";
fo<<"\n";
}
return 0;
}