Pagini recente » Cod sursa (job #1950547) | Cod sursa (job #1893238)
#include <bits/stdc++.h>
#define NMax 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M;
vector<int> Graf[NMax],sol[NMax];
int mark[NMax],low[NMax],nrSol,K,Stack[NMax];
void DFS(int nod,int tata)
{
mark[nod]=mark[tata]+1;
low[nod]=mark[nod];
Stack[K++]=nod;
for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
if(*it!=tata)
{
if(!mark[*it])
{
DFS(*it,nod);
low[nod]=min(low[nod],low[*it]);
if(mark[nod]<=low[*it])
{
while(K>0 && Stack[K-1]!=*it)
K--, sol[nrSol].push_back(Stack[K]);
K--;
sol[nrSol].push_back(Stack[K]);
sol[nrSol].push_back(nod);
nrSol++;
}
}
else
low[nod]=min(low[nod],mark[*it]);
}
}
int main()
{
fin>>N>>M;
for(int i=1;i<=M;i++)
{
int x,y;
fin>>x>>y;
Graf[x].push_back(y);
Graf[y].push_back(x);
}
for(int i=1;i<=N;i++)
if(!mark[i])
DFS(i,0);
fout<<nrSol<<"\n";
for(int i=0;i<nrSol;i++)
{
sort(sol[i].begin(),sol[i].end());
for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
fout<<*it<<" ";
fout<<"\n";
}
return 0;
}