Pagini recente » Cod sursa (job #2342657) | Cod sursa (job #497703) | Cod sursa (job #1534996) | Cod sursa (job #1939004) | Cod sursa (job #2758787)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
void dfs(int node, int& index, vector<int>& disc, vector<int>& lowlink, stack<pair<int, int>>& Edges, const vector<vector<int>>& graph, vector<vector<int>>& components){
disc[node] = lowlink[node] = ++index;
for(auto adjacent : graph[node]){
if(disc[adjacent] == -1){
Edges.push(pair<int, int>(node, adjacent));
dfs(adjacent, index, disc, lowlink, Edges, graph, components);
lowlink[node] = min(lowlink[node], lowlink[adjacent]);
if(lowlink[adjacent] >= disc[node]){
vector<int> component;
int x, y;
do{
x = Edges.top().first; y = Edges.top().second;
Edges.pop();
component.push_back(x);
component.push_back(y);
}while(!Edges.empty() && x != node && y != adjacent);
sort(component.begin(), component.end());
component.erase(unique(component.begin(), component.end()), component.end());
components.push_back(component);
}
}
else lowlink[node] = min(lowlink[node], disc[adjacent]);
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int N, M;
cin >> N >> M;
vector<vector<int>> graph;
vector<int> disc, lowlink;
for(int i = 0; i < N; ++i){
graph.push_back({});
disc.push_back(-1);
lowlink.push_back(-1);
}
for(int x, y; M > 0; --M){
cin >> x >> y;
--x; --y;
graph[x].push_back(y);
graph[y].push_back(x);
}
vector<vector<int>> components;
int index = 0;
for(int i = 0; i < N; ++i)
if(disc[i] == -1){
stack<pair<int, int>> Edges;
dfs(i, index, disc, lowlink, Edges, graph, components);
}
cout << components.size() << "\n";
for(auto component : components){
for(auto cmp : component)
cout << cmp + 1 << " ";
cout << "\n";
}
cin.close();
cout.close();
return 0;
}