Pagini recente » Cod sursa (job #2001625) | Cod sursa (job #124548) | Cod sursa (job #1869766) | Monitorul de evaluare | Cod sursa (job #3203025)
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;
void DFS(int nod, int depth, vector<vector<int>>& V,
stack<int>& S, vector<int>& dp, vector<int>& lvl, vector<int>& viz, vector<vector<int>>& comp) {
viz[nod] = 1;
lvl[nod] = depth;
dp[nod] = depth;
S.push(nod);
for (int neigh : V[nod]) {
if (viz[neigh] == 1) {
dp[nod] = min(dp[nod], lvl[neigh]);
}
else
if(viz[neigh] == 0){
DFS(neigh, depth + 1, V, S, dp, lvl, viz, comp);
dp[nod] = min(dp[nod], dp[neigh]);
if (dp[neigh] >= lvl[nod]) { // the edge from the child and its parent (the current node) is a bridge
vector<int> ans;
while (S.top() != nod) {
ans.push_back(S.top());
S.pop();
}
ans.push_back(nod);
comp.push_back(ans);
}
}
}
viz[nod] = 2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
f >> n >> m;
vector<vector<int>> V(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
f >> a >> b;
V[a].push_back(b);
V[b].push_back(a);
}
stack<int> S;
vector<int> dp(n + 1, 0), lvl(n + 1, 0), viz(n + 1, 0);
vector<vector<int>> comp;
DFS(1, 0, V, S, dp, lvl, viz, comp);
g << comp.size() << '\n';
for (vector<int>& ans : comp) {
for (int x : ans) g << x << ' ';
g << '\n';
}
return 0;
}