Pagini recente » Cod sursa (job #1676869) | Cod sursa (job #1462486) | Cod sursa (job #2025667) | Cod sursa (job #1723557) | Cod sursa (job #2796798)
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("dfs.in");
//ifstream fin("bfs.in");
//ifstream fin("sortaret.in");
//ifstream fin("biconex.in");
ifstream fin("ctc.in");
ofstream fout("ctc.out");
//ofstream fout("biconex.out");
//ofstream fout("sortaret.out");
//ofstream fout("bfs.out");
//ofstream fout("dfs.out");
const int N = 100010;
vector<int> nxt[N], prv[N], TOP;
int viz_1[N], viz_2[N]; // pentru componente tare conexe
class Graf {
private:
int n, m, nod_plecare;
vector<int> v[N];
vector<int> raspuns, Raspuns[N]; // folosite pentru a memora raspunsurile problemelor
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_1(int);
void dfs_2(int);
void dfs_comp_bi(int, int);
void afiseaza_componentele_biconexe();
void afiseaza_componentele_tare_conexe();
void bfs();
void citire_Graf_neorientat();
void citire_Graf_orientat();
void citire_Graf_orientat_tare_conexitate();
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_1(int node) {
viz_1[node] = 1;
for(auto it: nxt[node])
if(!viz_1[it])
dfs_1(it);
TOP.push_back(node);
}
void Graf::dfs_2(int node){
viz_2[node] = 1;
Raspuns[nr_sol].push_back(node);
for(auto it:prv[node])
if(!viz_2[it])
dfs_2(it);
}
void Graf::afiseaza_componentele_tare_conexe() {
for(int i=1;i<=n;i++)
if(!viz_1[i])
dfs_1(i);
reverse(TOP.begin(),TOP.end());
for(auto it:TOP)
if(!viz_2[it])
{
nr_sol++;
dfs_2(it);
}
fout<<nr_sol;
for(const auto &it:Raspuns)
{
for(auto elem:it)
fout<<elem<<" ";
fout<<'\n';
}
}
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::citire_Graf_orientat_tare_conexitate() {
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;
nxt[x].push_back(y);
prv[y].push_back(x);
}
}
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();
*/
Graf G;
G.citire_Graf_orientat_tare_conexitate();
G.afiseaza_componentele_tare_conexe();
return 0;
}