Pagini recente » Cod sursa (job #2645845) | Cod sursa (job #2473690) | Cod sursa (job #1127785) | Cod sursa (job #73690) | Cod sursa (job #2796747)
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("dfs.in");
//ifstream fin("bfs.in");
//ifstream fin("sortaret.in");
ifstream fin("biconex.in");
ofstream fout("biconex.out");
//ofstream fout("sortaret.out");
//ofstream fout("bfs.out");
//ofstream fout("dfs.out");
class Graf {
private:
static const int N = 100010;
int n, m, nod_plecare;
vector<int> v[N];
vector<int> raspuns, Raspuns[N];
int ans[N] = {0};
int intoarcere[N] = {0}, nivel[N] = {0}, st[N] = {0};
int top = 0, nr_sol = 0;
queue<pair<int, int>> q;
bitset<N> viz;
public:
Graf();
~Graf();
void add_edge(int, int);
void dfs(int);
void dfs_comp_bi(int, int);
void afiseaza_componentele_biconexe();
void bfs();
void citire_Graf_neorientat();
void citire_Graf_orientat();
void citire_Graf_orientat_bfs();
void sortare_topologica();
int nr_connected_components();
};
Graf::Graf() {
}
Graf::~Graf() {
}
void Graf::add_edge(int x, int y) {
v[x].push_back(y);
v[y].push_back(x);
}
void Graf::dfs(int node) {
viz[node] = 1;
for (auto it: v[node])
if (!viz[it])
dfs(it);
raspuns.push_back(node);
}
void Graf::dfs_comp_bi(int nod, int tata) {
intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
viz[nod] = 1;
top++;
st[top] = nod;
for (auto fiu: v[nod]) {
if (fiu == tata)
continue;
if (viz[fiu]) { // suntem intr-o muchie de intoarcere
intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
continue;
}
dfs_comp_bi(fiu,nod);
intoarcere[nod] = min(intoarcere[nod],intoarcere[fiu]);
if (intoarcere[fiu] >= nivel[nod]) {
nr_sol++;
while (st[top + 1] != fiu) {
Raspuns[nr_sol].push_back(st[top]);
top--;
}
Raspuns[nr_sol].push_back(nod);
}
}
}
void Graf::afiseaza_componentele_biconexe() {
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs_comp_bi(i, 0);
fout << this->nr_sol << '\n';
for (int i = 1; i <= nr_sol; i++) {
for (auto it: Raspuns[i])
fout << it << " ";
fout << '\n';
}
}
void Graf::sortare_topologica() {
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
for (vector<int>::reverse_iterator it = raspuns.rbegin(); it != raspuns.rend(); it++)
fout << (*it) << " ";
}
int Graf::nr_connected_components() {
int ct = 0;
for (int i = 1; i <= this->n; i++)
if (!viz[i]) {
dfs(i);
ct++;
}
return ct;
}
void Graf::citire_Graf_neorientat() {
int nr_noduri, nr_muchii;
fin >> nr_noduri >> nr_muchii;
this->n = nr_noduri;
this->m = nr_muchii;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void Graf::citire_Graf_orientat() {
int nr_noduri, nr_muchii;
fin >> nr_noduri >> nr_muchii;
(*this).n = nr_noduri;
(*this).m = nr_muchii;
for (int i = 1; i <= (*this).m; i++) {
int x, y;
fin >> x >> y;
v[x].push_back(y);
}
}
void Graf::citire_Graf_orientat_bfs() {
int nr_noduri, nr_muchii, plecare;
fin >> nr_noduri >> nr_muchii >> plecare;
this->n = nr_noduri;
this->m = nr_muchii;
this->nod_plecare = plecare;
q.push(make_pair(this->nod_plecare, 0));
for (int i = 1; i <= this->m; i++) {
int x, y;
fin >> x >> y;
v[x].push_back(y);
}
}
void Graf::bfs() {
while (!q.empty()) {
pair<int, int> dp = q.front();
int x = dp.first;
int y = dp.second;
ans[x] = y;
for (auto it: v[x])
if (!viz[it]) {
viz[it] = 1;
q.push(make_pair(it, y + 1));
}
q.pop();
}
ans[this->nod_plecare] = 0;
for (int i = 1; i <= n; i++) {
if (ans[i] == 0 && i != this->nod_plecare)
ans[i] = -1;
fout << ans[i] << " ";
}
}
int main() {
/*
Graf G;
G.citire_Graf_neorientat();
fout<<G.nr_connected_components();
*/
/*
Graf G;
G.citire_Graf_orientat_bfs();
G.bfs();
*/
/*
Graf G;
G.citire_Graf_orientat();
G.sortare_topologica();
*/
Graf G;
G.citire_Graf_neorientat();
G.afiseaza_componentele_biconexe();
return 0;
}