Pagini recente » Cod sursa (job #613721) | Cod sursa (job #683551) | Cod sursa (job #116942) | Cod sursa (job #886411) | Cod sursa (job #2811672)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <set>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int INF = 2e9;
int n, m, cont;
int tin[100005], low[100005];
vector<int> adj[100005];
vector<set<int>> cbc;
stack<pair<int, int>> s;
void addComp(int x, int y)
{
set<int> comp;
while(!s.empty() && (s.top().first != x || s.top().second != y))
{
comp.insert(s.top().first);
comp.insert(s.top().second);
s.pop();
}
comp.insert(s.top().first);
comp.insert(s.top().second);
s.pop();
cbc.push_back(comp);
}
void dfs(int node, int father = 0)
{
tin[node] = low[node] = ++cont;
for(auto it: adj[node])
{
if(node == father)
continue;
if(tin[it] != 0)
low[node] = min(low[node], tin[it]);
else
{
s.push({node, it});
dfs(it, node);
low[node] = min(low[node], low[it]);
if(low[it] >= tin[node])
addComp(node, it);
}
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
memset(tin, INF, sizeof tin);
dfs(1);
out << cbc.size() << '\n';
for(auto it: cbc)
{
for(auto it2: it)
out << it2 << ' ';
out << '\n';
}
return 0;
}