Pagini recente » Cod sursa (job #1713406) | Cod sursa (job #1098669) | Cod sursa (job #2390584) | Cod sursa (job #564138) | Cod sursa (job #613041)
Cod sursa(job #613041)
#include<fstream>
#include<vector>
#define inf 100000
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> graph[inf];
int n,m,nv[inf],low[inf],t[inf],ras[inf],u[inf],rad,nr;
void df(int nod)
{
u[nod]=1;
low[nod]=nv[nod];
for(int i=0;i<graph[nod].size();i++)
{
int child=graph[nod][i];
if(u[child]!=1)
{
t[child]=nod;
nv[child]=nv[nod]+1;
if(nod==rad)nr++;
df(child);
if(low[child]<low[nod]) low[nod]=low[child];
if(low[child]>=nv[nod]) ras[nod]=1;
}
else if(child!=t[nod]&&low[nod]>=nv[child]) low[nod]=nv[child];
}
}
int main()
{
in >> n >>m;
for(int i=0;i<m;i++)
{
int x,y;
inf >> x >>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(u[i]!=1)
{
nv[i]=1;
rad =i;
nr=0;
df(i);
if(nr>1)ras[rad]=1;
}
}
int nrras=0;
for(int i=1;i<=n;i++) if(ras[i]==1)nrras++;
out << nrras <<'\n';
for(int i=1;i<=n;i++) if(ras[i]==1)
{
out <<i<<' ';
for(int j=0;j<graph[i].size();j++)out<<graph[i][j]<<' ';
out<<'\n';
}
}