Pagini recente » Cod sursa (job #1678033) | Cod sursa (job #2514405) | Cod sursa (job #1999491) | Cod sursa (job #2217950) | Cod sursa (job #3303135)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template<typename A,typename B>ostream&operator<<
(ostream &out,const pair<A,B>&x){return cout<<x.
first<<' '<<x.second;}void debug(const char*str){
cout<<str;}template<typename T,typename...Args>
void debug(const char*str,T x,Args...args){while(
*str!='\0'){if(*str=='%'){cout<<x;debug(str+1,args
...);return;}else cout<<*str;++str;}}
#else
#define debug
#endif
vector<int> v[100005];
stack<pair<int,int>> st;
bitset<100005> bit;
int depth[100005], up[100005];
vector<vector<int>> comp;
void build(int a, int b)
{
debug("% %\n", a, b);
comp.push_back(vector<int>());
while(!st.empty())
{
comp.back().push_back(st.top().first);
comp.back().push_back(st.top().second);
if(st.top() == make_pair(a, b))
{
st.pop();
break;
}
st.pop();
}
sort(comp.back().begin(), comp.back().end());
comp.back().erase(unique(comp.back().begin(), comp.back().end()), comp.back().end());
}
void dfs(int node)
{
bit[node] = 1;
up[node] = depth[node];
for(const auto &i : v[node])
{
if(depth[i] == depth[node] - 1)
continue;
if(bit[i])
up[node] = min(up[node], depth[i]);
else
{
st.emplace(node, i);
depth[i] = depth[node] + 1;
dfs(i);
up[node] = min(up[node], up[i]);
if(up[i] >= depth[node])
build(node, i);
}
}
}
signed main()
{
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
int n, m; fin>>n>>m;
for(int i=0; i<m; ++i)
{
int a, b; fin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
depth[1] = 2;
dfs(1);
fout<<comp.size()<<'\n';
for(auto &i : comp)
{
for(auto &j : i)
fout<<j<<' ';
fout<<'\n';
}
return 0;
}