Pagini recente » Cod sursa (job #66507) | Cod sursa (job #2867270) | Cod sursa (job #54291) | Cod sursa (job #2472620) | Cod sursa (job #3225607)
#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];
/* low[node] = cel mai inalt nivel la carepputem ajunge
dintr un nod din subarborele lui node printr -o
SINGURA muchie de intoarcere
*/
// 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(node != 1 && low[node] >= h[parent[node]])
{
// cout << parent[node] << " " << node << " " << low[node] << " " << h[parent[node]] << " a\n";
++cnt;
while(!st.empty() && st.top() != node)
{
components[cnt].push_back(st.top());
st.pop();
}
st.pop();
components[cnt].push_back(node);
components[cnt].push_back(parent[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;
}