Pagini recente » Cod sursa (job #288806) | Cod sursa (job #150927) | Cod sursa (job #594763) | Cod sursa (job #2498700) | Cod sursa (job #1413672)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct Node
{
int index;
int parent;
int lowlink;
bool on_stack;
};
vector<Node> nodes;
vector<vector<int>> edges;
unsigned index = 0;
stack<int> nodes_unass;
vector<vector<int>> components;
void biconex(int v) {
nodes[v].index = index++;
nodes[v].lowlink = nodes[v].index;
nodes_unass.push(v);
nodes[v].on_stack = true;
for(int u:edges[v]) {
if(nodes[u].index == -1) {
nodes[u].parent = v;
biconex(u);
nodes[v].lowlink = min(nodes[v].lowlink,nodes[u].lowlink);
if(nodes[u].lowlink >= nodes[v].index) {
components.push_back(vector<int>({v}));
while(nodes_unass.top() != v) {
nodes[nodes_unass.top()].on_stack = false;
components.back().push_back(nodes_unass.top());
nodes_unass.pop();
}
}
}
else if (u != nodes[v].parent) {
nodes[v].lowlink = min(nodes[v].lowlink,nodes[u].index);
}
}
}
int main() {
int n,m;
in >> n >> m;
edges.resize(n+1);
nodes.resize(n+1,{-1,-1});
for(int i = 0; i < m; ++i) {
int a,b;
in >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
for(int i = 1; i <= n; ++i) {
if(nodes[i].index == -1) {
biconex(i);
}
}
out << components.size() << '\n';
for(auto comp:components) {
for(int v:comp) {
out << v << ' ';
}
out << '\n';
}
return 0;
}