Pagini recente » Cod sursa (job #619976) | Cod sursa (job #677476) | Cod sursa (job #692830) | Cod sursa (job #2534503) | Cod sursa (job #3236379)
#include <bits/stdc++.h>
#define VMAX 100
#define NMAX 100000
#define LOG 21
#define INF (int)(10e8)
#define MOD 1000000007
#define ll long long int
#define x first
#define y second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,k;
vector<int> adj[NMAX+1],compb[NMAX+1];
bool vis[NMAX+1];
int niv[NMAX+1],nma[NMAX+1];
stack<int> S;
void dfs(int x,int tx)
{
vis[x]=1;
niv[x]=niv[tx]+1;
nma[x]=niv[x];
S.push(x);
for(int i : adj[x])
{
if(vis[i]&&i!=tx)
{
nma[x]=min(nma[x],niv[i]);
}
else if(!vis[i])
{
dfs(i,x);
nma[x]=min(nma[x],nma[i]);
if(niv[x]<=nma[i])
{
++k;
while(S.top()!=i)
{
compb[k].push_back(S.top());
S.pop();
}
compb[k].push_back(S.top());
S.pop();
compb[k].push_back(x);
}
}
}
}
int main()
{
int n,m;
fin >> n >> m;
while(m--)
{
int x,y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1,0);
bool conex=1;
for(int i=1;i<=n;i++)
{
conex &= vis[i];
}
if(!conex)
{
fout << 0;
return 0;
}
fout << k << "\n";
for(int i=1;i<=k;i++)
{
for(int j : compb[i])
{
fout << j << " ";
}
fout << "\n";
}
}