Pagini recente » Cod sursa (job #3002294) | Cod sursa (job #46077) | Cod sursa (job #3140162) | Cod sursa (job #2690557) | Cod sursa (job #2123501)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[nmax];
stack <pair<int,int> > s;
int t[nmax],viz[nmax],low[nmax],niv[nmax],r,sol[nmax],sl[nmax],nr,n,m,x,y,num;
void df(int i)
{
viz[i]=1;
low[i]=niv[i];
for(int j=0; j<v[i].size(); j++)
{
if(v[i][j]!=t[i]&&niv[i]>niv[v[i][j]])
s.push({i,v[i][j]});
if(!viz[v[i][j]])
{
niv[v[i][j]]=niv[i]+1;
t[v[i][j]]=i;
df(v[i][j]);
low[i]=min(low[i],low[v[i][j]]);
if(low[v[i][j]]>=niv[i])
num++;
}
else if(v[i][j]!=t[i]) low[i]=min(low[i],niv[v[i][j]]);
}
}
void df2(int i)
{
viz[i]=1;
low[i]=niv[i];
for(int j=0; j<v[i].size(); j++)
{
if(v[i][j]!=t[i]&&niv[i]>niv[v[i][j]])
s.push({i,v[i][j]});
if(!viz[v[i][j]])
{
niv[v[i][j]]=niv[i]+1;
t[v[i][j]]=i;
df2(v[i][j]);
low[i]=min(low[i],low[v[i][j]]);
if(low[v[i][j]]>=niv[i])
{
int k=0;
do{
x=s.top().first;
y=s.top().second;
s.pop();
sol[++k]=x;
sol[++k]=y;
}while(!s.empty()&&(x!=i||y!=v[i][j])&&(y!=i||x!=v[i][j]));
sort(sol+1,sol+k+1);
for(int j1=1;j1<=k;j1++)
if(sol[j1]!=sol[j1-1]) g<<sol[j1]<<' ';
g<<'\n';
}
}
else if(v[i][j]!=t[i]) low[i]=min(low[i],niv[v[i][j]]);
}
}
int main()
{
int i;
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; i++)
if(!viz[i])
{
r=i;
nr=0;
niv[i]=1;
df(i);
if(nr>1) sol[r]=1;
else sol[r]=0;
}
g<<num<<'\n';
for(i=1;i<=n;i++) viz[i]=niv[i]=low[i]=t[i]=0;
for(i=1; i<=n; i++)
if(!viz[i])
{
r=i;
nr=0;
sl[++num]=i;
niv[i]=1;
df2(i);
}
return 0;
}