Pagini recente » Cod sursa (job #2845618) | Cod sursa (job #176698) | Cod sursa (job #1881153) | Cod sursa (job #1541540) | Cod sursa (job #2197964)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
get_result();
print_output();
}
private:
struct Edge {
int x;
int y;
};
int n;
int m;
vector<int> adj[kNmax];
vector<int> parent;
vector<int> idx;
vector<int> lowLink;
int timp;
stack<Edge> stiva;
set<int> _set;
vector<set<int>> componente;
void read_input() {
ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void DFS(int nod) {
idx[nod] = lowLink[nod] = ++timp;
vector<int>::iterator it;
for (it = adj[nod].begin(); it != adj[nod].end(); ++it) {
if (*it != parent[nod]) {
if (!idx[*it]) {
parent[*it] = nod;
stiva.push({ nod, *it });
DFS(*it);
if (lowLink[nod] > lowLink[*it]) {
lowLink[nod] = lowLink[*it];
}
if (idx[nod] <= lowLink[*it]) {
int x, y;
componente.push_back(_set);
set<int> &v = componente[componente.size()-1];
do {
x = stiva.top().x;
y = stiva.top().y;
stiva.pop();
v.insert(x);
v.insert(y) ;
} while (x != nod && y != nod);
// muchie critica - deci capetele formeaza o componenta biconexa
}
}
else { // intotdeauna gri ptr grafuri neorientate
if (lowLink[nod] > idx[*it])
lowLink[nod] = idx[*it];
}
}
}
}
void get_result() {
for (int i = 0; i <= n; ++i) {
parent.push_back(0);
idx.push_back(0);
lowLink.push_back(0);
}
for (int i = 1; i <= n; ++i) {
timp = 0;
if (!idx[i]) {
DFS(i);
}
}
}
void print_output() {
ofstream fout("biconex.out");
fout << componente.size() << '\n';
for (const auto& ctc : componente) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}