Pagini recente » Cod sursa (job #943620) | Cod sursa (job #2068295) | Cod sursa (job #613814) | Cod sursa (job #227719) | Cod sursa (job #3225573)
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000
const int INF = 1e9;
int n, m, cnt;
bitset < MAX_N + 1> viz;
stack <int> st;
vector <int> low, parent, h;
vector <vector <int> > graph, components;
void isBridge(int a, int b)
{
cout << "isBridge\n";
cout << a << " " << b << "\n";
}
void isCutpoint(int a)
{
cout << "isCutpoint\n";
cout << a << "\n";
}
void dfs(int node)
{
st.push(node);
viz[node] = 1;
h[node] = h[parent[node]] + 1;
low[node] = h[node];
// cout << node << "\n";
// cout << low[node] << " aa\n";
for(const int &x : graph[node])
{
if(viz[x])
{
if(x != parent[node])
low[node] = min(low[node], h[x]);
}
else
{
parent[x] = node;
dfs(x);
low[node] = min(low[node], low[x]);
if(low[x] >= h[node])
{
++cnt;
while(st.top() != node)
{
components[cnt].push_back(st.top());
st.pop();
}
components[cnt].push_back(node);
}
}
}
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin >> n >> m;
graph.resize(n + 1);
for(int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
low.resize(n + 1, INF);
parent.resize(n + 1);
h.resize(n + 1);
components.resize(n + 1);
dfs(1);
cout << cnt << "\n";
for(int i = 1; i <= cnt; i ++)
{
for(const int &x : components[i])
cout << x << " ";
cout << "\n";
}
// for(int i = 1; i <= n; i ++)
// cout << i << " " << low[i] <<"\n";
return 0;
}