Pagini recente » Cod sursa (job #2596898) | Cod sursa (job #1286926) | Cod sursa (job #652452) | Cod sursa (job #2924466) | Cod sursa (job #2197933)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<int> adj[kNmax];
//vector<int> color;
//vector<int> critic;
vector<int> parent;
vector<int> idx;
vector<int> lowLink;
int timp;
stack<int> stiva;
void read_input() {
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void DFS(vector<vector<int>> &componente, int nod) {
//color[nod] = 1;
idx[nod] = lowLink[nod] = ++timp;
vector<int>::iterator it;
stiva.push(nod);
//int childCounter = 0;
for (it = adj[nod].begin(); it != adj[nod].end(); ++it) {
if (*it != parent[nod]) {
//if (!color[*it]) {
if (!idx[*it]) {
//childCounter++;
parent[*it] = nod;
DFS(componente, *it);
if (lowLink[nod] > lowLink[*it]) {
lowLink[nod] = lowLink[*it];
}
}
else { // intotdeauna gri ptr grafuri neorientate
if (lowLink[nod] > idx[*it])
lowLink[nod] = idx[*it];
}
}
}
if (idx[nod] == lowLink[nod]) {
vector<int> v;
int x;
do {
x = stiva.top();
v.push_back(x);
//color[x] = 2;
stiva.pop();
} while (x != nod);
//componente.push_back(v);
}
}
vector<vector<int>> get_result() {
for (int i = 0; i <= n; ++i) {
//color.push_back(0);
//critic.push_back(0);
parent.push_back(0);
idx.push_back(0);
lowLink.push_back(0);
}
vector<vector<int>> componente;
for (int i = 1; i <= n; ++i) {
//if (!color[i]) {
timp = 0;
if (!idx[i]) {
DFS(componente, i);
}
}
/*
TODO: Gasiti muchiile critice ale grafului neorientat stocat cu liste
de adiacenta in adj.
*/
return componente;
}
void print_output(vector<vector<int>> result) {
cout << result.size() << '\n';
for (const auto& ctc : result) {
for (int nod : ctc) {
cout << nod << ' ';
}
cout << '\n';
}
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}