Pagini recente » Cod sursa (job #1379918) | Cod sursa (job #2192868) | Cod sursa (job #3245508) | Cod sursa (job #2951773) | Cod sursa (job #1970048)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define inf 0x3f3f3f3f
int n, m, a, b, idx, k;
vector<vector<int>> G, cc;
vector<int> L, Idx, c;
stack<pair<int, int>> Stk;
void Save(int x, int y) {
c.clear();
int nodx, nody;
do {
nodx = Stk.top().first;
nody = Stk.top().second;
c.push_back(nodx);
c.push_back(nody);
Stk.pop();
} while(nodx != x || nody != y);
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
cc.push_back(c);
}
void Tarjan(const int& nod, const int& t) {
Idx[nod] = L[nod] = idx++;
for(const int& y : G[nod])
if(Idx[y] == inf) {
Stk.push({nod, y});
Tarjan(y, nod);
L[nod] = min(L[nod], L[y]);
if(L[y] >= Idx[nod])
Save(nod, y);
} else
if(y != t)
L[nod] = min(L[nod], Idx[y]);
}
int main()
{
fin >> n >> m;
G = vector<vector<int>> (n + 1);
L = vector<int> (n + 1);
Idx = vector<int> (n + 1, inf);
for(int i = 1; i <= m; ++i) {
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; ++i)
if(Idx[i] == inf)
Tarjan(i, 0);
fout << cc.size() << '\n';
for(int i = 0; i < cc.size(); ++i) {
for(int x : cc[i])
fout << x << ' ';
fout << '\n';
}
return 0;
}