Pagini recente » Cod sursa (job #1977179) | Cod sursa (job #470411) | Cod sursa (job #715400) | Cod sursa (job #699301) | Cod sursa (job #3295211)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack<pair<int, int>> st;
vector<vector<int>> megoldas;
const int INF = 1000*1000*1000;
void DFS(vector<vector<int>> &adj, int node, vector<int> &low, vector<int> &disc, int parent, int t)
{
disc[node] = t;
low[node] = t;
for(int i = 0; i < adj[node].size(); i++){
int newNode = adj[node][i];
if(newNode == parent){
continue;
}
if(disc[newNode] == INF){
st.push({node, newNode});
DFS(adj, newNode, low, disc, node, t+1);
low[node] = min(low[node], low[newNode]);
if(low[newNode] >= disc[node]){
pair<int, int> curr = st.top();
st.pop();
vector<int> temp;
temp.push_back(curr.first);
temp.push_back(curr.second);
while(curr.first != node || curr.second != newNode){
curr = st.top();
st.pop();
temp.push_back(curr.first);
temp.push_back(curr.second);
}
megoldas.push_back(temp);
}
}
else{
low[node] = min(low[node], disc[newNode]);
}
}
}
int main()
{
int N, M;
fin >> N >> M;
vector<vector<int>> adj(N+2);
for(int i = 0; i < M; i++){
int a, b;
fin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> disc(N+1, INF);
vector<int> low(N+1, INF);
vector<int> parent(N+1, -1);
for(int i = 1; i <= N; i++){
if(disc[i] == INF){
DFS(adj, i, low, disc, 0, 0);
}
}
fout << megoldas.size() << endl;
for(int i = 0; i < megoldas.size(); i++){
sort(megoldas[i].begin(), megoldas[i].end());
megoldas[i].erase(unique(megoldas[i].begin(), megoldas[i].end()), megoldas[i].end());
for(int j = 0; j < megoldas[i].size(); j++){
fout << megoldas[i][j] << " ";
}
fout << endl;
}
return 0;
}