Pagini recente » Cod sursa (job #2686213) | Cod sursa (job #910034) | Borderou de evaluare (job #201322) | Borderou de evaluare (job #137777) | Cod sursa (job #2397711)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
struct nod
{
int v;
nod *next;
}*a[NMAX];
int ap[NMAX],nivel[NMAX],nma[NMAX],nrcomp;
stack<int> stk;
vector<int> out[NMAX];
void dfs(int x,int tata)
{
ap[x]=true;
stk.push(x);
nivel[x]=nivel[tata]+1;
nma[x]=nivel[x];
for (nod* j=a[x];j;j=j->next)
if (j->v!=tata)
{
if (ap[j->v]==true)
{
///muchie de intoarcere
if (nma[x]>nivel[j->v])
nma[x]=nivel[j->v];
}
else
{
///muchie normala
dfs(j->v,x);
if (nma[x]>nma[j->v])
nma[x]=nma[j->v];
if (nivel[x]<=nma[j->v])
{
nrcomp++;
while(stk.top()!=j->v)
{
out[nrcomp].push_back(stk.top());
stk.pop();
}
out[nrcomp].push_back(j->v);
stk.pop();
out[nrcomp].push_back(x);
}
}
}
}
int main()
{
int n,m;
fin>>n>>m;
for (int i=0;i<m;i++)
{
int x,y;
fin>>x>>y;
nod *nou=new nod;
nou->v=y;
nou->next=a[x];
a[x]=nou;
nou=new nod;
nou->v=x;
nou->next=a[y];
a[y]=nou;
}
dfs(1, 0);
fout<<nrcomp<<'\n';
for(int i=1;i<=nrcomp;i++)
{
for(auto& value : out[i])
fout<<value<<' ';
fout<<'\n';
}
return 0;
}