Mai intai trebuie sa te autentifici.
Cod sursa(job #2204704)
Utilizator | Data | 16 mai 2018 21:00:29 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.52 kb |
#include <iostream>
#include <fstream>
#include <vector>
#define dMAX 100000
using namespace std;
int p, n, m;
int x, y, r;
int counter;
vector<int> graf[dMAX + 2];
bool viz[dMAX + 2];
int d[dMAX + 2], L[dMAX + 2];
int myStack[dMAX + 2], h;
vector<int> componente[dMAX + 2];
int cindx;
vector<int> critice;
bool crit[dMAX + 2];
vector<pair<int, int> > muchii;
ifstream fin("componentebiconexe.in");
ofstream fout("componentebiconexe.out");
void DFS(int v, int pv) {
int newV, u;
viz[v] = true;
myStack[++h] = v;
d[v] = d[pv] + 1;
L[v] = d[v];
if (d[v] == 2) counter++;
for (u = 0; u < graf[v].size(); u++) {
newV = graf[v][u];
if (newV != pv) {
if (viz[newV]) {
L[v] = min(d[newV], L[v]);
} else {
DFS(newV, v);
L[v] = min(L[newV], L[v]);
/// Cerinta 1
if (L[newV] >= d[v]) {
cindx++;
componente[cindx].push_back(v);
while (myStack[h] != newV) {
componente[cindx].push_back(myStack[h--]);
}
componente[cindx].push_back(myStack[h--]);
}
/// Cerinta 2
if (L[newV] >= d[v] && v != r) {
if (!crit[v])
critice.push_back(v), crit[v] = true;
}
/// Cerinta 3
if (L[newV] > d[v]) {
muchii.push_back({v, newV});
}
}
}
}
}
int main()
{
int i, j;
//fin >> p;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
r = 1;
DFS(1, 0);
//if (p == 1) {
fout << cindx << '\n';
for (i = 1; i <= cindx; i++) {
//fout << componente[i].size() << ' ';
for (j = 0; j < componente[i].size(); j++) {
fout << componente[i][j] << ' ';
}
fout << '\n';
}
/*} else if (p == 2) {
if (counter > 1) critice.push_back(r);
fout << critice.size() << '\n';
for (i = 0; i < critice.size(); i++) fout << critice[i] << ' ';
} else {
fout << muchii.size() << '\n';
for (i = 0; i < muchii.size(); i++) {
fout << muchii[i].first << ' ' << muchii[i].second << '\n';
}
}*/
return 0;
}