Pagini recente » Cod sursa (job #1449693) | Cod sursa (job #2446860) | Cod sursa (job #2730546) | Cod sursa (job #1454171) | Cod sursa (job #2870871)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
vector <int> v[100005],ceau[100005];
int l[100005],viz[100005];
int niv[100005],nrcomp,tata[100005];
stack <pair <int,int>> deq;
void dfs(int x,int nivel)
{
viz[x]=1;
l[x]=nivel;
niv[x]=nivel;
for (int i=0;i<v[x].size();i++)
{
int nod =v[x][i];
if (viz[nod]==0)
{
int sal1 = min(nod,x);
int sal2 = max(nod,x);
deq.push({sal1,sal2});
tata[nod]=x;
dfs(nod,nivel+1);
if (l[x]>l[nod])
{
l[x]=l[nod];
}
if (l[nod]>=niv[x])
{
if (deq.empty())
{
continue;
}
nrcomp++;
while (1)
{
int x2 = deq.top().first;
int y2 = deq.top().second;
ceau[nrcomp].push_back(x2);
ceau[nrcomp].push_back(y2);
deq.pop();
if (x2==sal1||y2==sal2)
{
break;
}
}
}
}
else
{
if (nod!=tata[x]&&l[x]>niv[nod])
{
l[x]=niv[nod];
}
}
}
}
int i,j;
int main()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for (i=1;i<=n;i++)
{
if (viz[i]==0)
{
dfs(i,0);
}
}
g<<nrcomp<<'\n';
for (i=1;i<=nrcomp;i++)
{
sort (ceau[i].begin(),ceau[i].end());
g<<ceau[i][0]<<" ";
for (j=1;j<ceau[i].size();j++)
{
if (ceau[i][j]!=ceau[i][j-1])
{
g<<ceau[i][j]<<" ";
}
}
g<<'\n';
}
return 0;
}