Pagini recente » Cod sursa (job #1665435) | Cod sursa (job #2346100) | Cod sursa (job #2532503) | Cod sursa (job #1095561) | Cod sursa (job #3295208)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack<pair<int, int>> st;
int time = 1;
vector<vector<int>> megoldas;
const int INF = 1000*1000*1000;
void DFS(vector<vector<int>> &adj, int node, vector<int> &low, vector<int> &disc, vector<int> &parent, vector<vector<int>> &adj_new)
{
disc[node] = time;
low[node] = time;
time++;
int children = 0;
for(int i = 0; i < adj[node].size(); i++){
int newNode = adj[node][i];
if(newNode == parent[node]){
continue;
}
if(disc[newNode] == INF){
st.push({node, newNode});
DFS(adj, newNode, low, disc, parent, adj_new);
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);
}
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+1), adj_new(N+1);
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++){
time = 1;
if(disc[i] == INF){
DFS(adj, i, low, disc, parent, adj_new);
}
}
fout << megoldas.size() << endl;
for(int i = 0; i < megoldas.size(); i++){
for(int j = 0; j < megoldas[i].size(); j++){
fout << megoldas[i][j] << " ";
}
fout << endl;
}
return 0;
}