Pagini recente » Cod sursa (job #834612) | Cod sursa (job #2001127) | Cod sursa (job #2038819) | Cod sursa (job #1350706) | Cod sursa (job #2150245)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <bitset>
#define NM 100005
#define pb push_back
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,level[NM],lowlink[NM];
stack<pair<int,int> > st;
vector<int> g[NM];
bitset<NM> viz;
set<int> s;
vector<int > v;
int caz,sol;
void getBcc(int node,int son)
{
int x,y;
do
{
x=st.top().first;
y=st.top().second;
s.insert(x);
s.insert(y);
st.pop();
}
while(node!=x || son!=y);
for(auto i:s)out<<i<<" ";
out<<'\n';
s.clear();
}
void dfs(int node,int father)
{
viz[node]=1;
level[node]=level[father]+1;
lowlink[node]=level[node];
for(auto fiu:g[node])
{
if(!viz[fiu])
{
st.push({node,fiu});
dfs(fiu,node);
lowlink[node]=min(lowlink[node],lowlink[fiu]);
if(lowlink[fiu]>=level[node])
{
if(caz==1)++sol;
else getBcc(node,fiu);
}
}
else
{
if(fiu!=father)
lowlink[node]=min(lowlink[node],level[fiu]);
}
}
}
int main()
{
in>>n>>m;
while(m--)
{
int x,y;
in>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
caz=1;
dfs(1,0);
for(int i=1;i<=n;++i)viz[i]=level[i]=lowlink[i]=0;
while(!st.empty())st.pop();
out<<sol<<'\n';
caz=2;
dfs(1,0);
return 0;
}