Pagini recente » Cod sursa (job #1608974) | Cod sursa (job #668317) | Cod sursa (job #1848912) | Cod sursa (job #758202) | Cod sursa (job #2150216)
#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;
vector<set<int> > comp;
void getBcc(int node,int son)
{
set<int> s;
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);
comp.pb(s);
}
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])
{
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);
}
dfs(1,0);
out<<comp.size()<<'\n';
for(auto s:comp)
{
for(auto i:s)out<<i<<" ";
out<<'\n';
}
return 0;
}