Pagini recente » Cod sursa (job #1451940) | Cod sursa (job #1259944) | Cod sursa (job #458068) | Cod sursa (job #981444) | Cod sursa (job #2499996)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr,num,start = 1;
int dfn[100001],low[100001];
int fr[10000][10000];
vector<vector<int>> a(100001,vector<int>());
vector<vector<int>> componente(100001,vector<int>());
struct Muchie{
int f;
int t;
};
stack<Muchie> S;
void Citire()
{
f>>n>>m;
int x,y;
for(int i=1;i<=m;++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void Initializare()
{
for(int i=1;i<=n;++i) dfn[i] = low[i] = -1;
S.push({start,-1});
}
void Pastrare(int x,int u)
{
++nr;
Muchie p;
do{
p = S.top();
if(fr[nr][p.f] == false) componente[nr].push_back(p.f),fr[nr][p.f] = true;
if(fr[nr][p.t] == false) componente[nr].push_back(p.t),fr[nr][p.t] = true;
S.pop();
}while(p.f != x && p.t != u);
}
void Biconex(int u, int tu)
{
dfn[u] = low[u] = ++num;
for(vector<int>::iterator it=a[u].begin();it!=a[u].end();++it)
{
if(*it != tu && dfn[*it] < dfn[u]) S.push({*it,u});
if(dfn[*it] == -1)
{
Biconex(*it,u);
low[u] = min(low[*it],low[u]);
if(low[*it] >= dfn[u])
Pastrare(*it,u);
}
else
{
if(*it != tu)
low[u] = min(low[u],dfn[*it]);
}
}
}
int main()
{
Citire();
Initializare();
Biconex(start,-1);
g<<nr<<'\n';
for(int i=1;i<=nr;++i)
{
for(vector<int>::iterator it=componente[i].begin();it!=componente[i].end();++it)
g<<*it<<" ";
g<<'\n';
}
return 0;
}