Pagini recente » Cod sursa (job #379662) | Cod sursa (job #177169) | Cod sursa (job #1705543) | Diferente pentru utilizator/blattraditional intre reviziile 7 si 6 | Cod sursa (job #1339512)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#define DIM 100005
#define vint vector<int>::iterator
#define infile "biconex.in"
#define outfile "biconex.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int n, m;
bool ok[DIM];
int Niv[DIM], Low[DIM];
int nrBiConexe;
vector<int> L[DIM], biConexe[DIM];
stack<int> Stack;
void DFS(int node, int lvl) {
ok[node] = 1;
Niv[node] = lvl;
Low[node] = lvl;
Stack.push(node);
for (vint it = L[node].begin(); it != L[node].end(); ++it) {
if (ok[*it]) {
Low[node] = std::min(Low[node], Niv[*it]);
continue;
}
DFS(*it, lvl + 1);
Low[node] = std::min(Low[node], Low[*it]);
if (Niv[node] <= Low[*it]) {
++nrBiConexe;
int x;
do {
x = Stack.top();
Stack.pop();
biConexe[nrBiConexe].push_back(x);
} while (x != *it);
biConexe[nrBiConexe].push_back(node);
}
}
}
int main() {
f >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
f >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
memset(ok, false, sizeof(ok));
for (int i = 1; i <= n; ++i)
if (!ok[i])
DFS(i, 1);
g << nrBiConexe << '\n';
for (int i = 1; i <= nrBiConexe; ++i) {
for (vint it = biConexe[i].begin(); it != biConexe[i].end(); ++it)
g << *it << ' ';
g << '\n';
}
return 0;
}
//Trust me, I'm the Doctor!