Pagini recente » Cod sursa (job #607322) | Cod sursa (job #400615) | Cod sursa (job #1928923) | Cod sursa (job #1530301) | Cod sursa (job #1931678)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
stack <pair <int, int> > stk;
vector <vector <int> >C;
vector <int> G[100005];
int Time[100005], lowTime[100005], IX, edges, nodes;
void print(int node, int it) {
vector <int> con; int tx, ty;
do {
tx = stk.top().first;
ty = stk.top().second;
stk.pop();
con.push_back(tx);
con.push_back(ty);
}
while (tx != node || ty != it);
C.push_back(con);
}
void DFS (int node, int parent) {
Time[node] = IX;
lowTime[node] = IX;
++ IX;
for (auto &it: G[node]) {
if (it == parent) continue;
if (Time[it] == -1) {
stk.push (make_pair (node, it));
DFS (it, node);
lowTime[node] = min (lowTime[node], lowTime[it]);
if (lowTime[it] >= Time[node]) {
print (node, it);
}
}
else {
lowTime[node] = min (lowTime[node], Time[it]);
}
}
}
int main()
{
in >> nodes >> edges;
for (int i = 1; i <= edges; ++ i) {
int node1, node2;
in >> node1 >> node2;
G[node1].push_back (node2);
G[node2].push_back (node1);
}
for (int i = 1; i <= nodes; ++ i) {
Time[i] = -1;
}
DFS (4, 0);
out << C.size() << "\n";
for (size_t i = 0; i < C.size(); ++ i) {
sort(C[i].begin(), C[i].end());
C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
for (size_t j = 0; j < C[i].size(); ++ j)
out << C[i][j] << " ";
out << "\n";
}
return 0;
}