Pagini recente » Cod sursa (job #2528661) | Rating Constantin Cosmin (Kira) | Cod sursa (job #2685174) | Cod sursa (job #1431669) | Cod sursa (job #2698241)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,h[100005],low[100005],cnt;
vector<int> muchii[100005],cmp[100005];
bool use[100005];
stack<int> s;
void comp(int curent, int nxt)
{
cnt++;
while(s.top()!=nxt)
{
cmp[cnt].push_back(s.top());
s.pop();
}
cmp[cnt].push_back(nxt);
cmp[cnt].push_back(curent);
s.pop();
}
void dfs(int nod,int father,int height)
{
low[nod]=h[nod]=height;
s.push(nod);
for(auto i:muchii[nod])
{
if(!h[i])
{
dfs(i,nod,height+1);
low[nod]=min(low[nod],low[i]);
if(low[i]>=height)
comp(nod,i);
}
else if(i!=father)
low[nod]=min(low[nod],h[i]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
fin>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!h[i])
dfs(i,-1,1);
fout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
for(auto j:cmp[i])
fout<<j<<' ';
fout<<'\n';
}
return 0;
}