Pagini recente » Cod sursa (job #1710451) | Cod sursa (job #722470) | Cod sursa (job #3194037) | Rating Nicu Scurtu (F0xyshor) | Cod sursa (job #3226790)
// https://www.infoarena.ro/problema/ctc
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAX_N = 100005;
struct t_coada {
int elems[MAX_N];
int idx;
};
void init_coada(t_coada& coada) {
coada.idx = -1;
}
void push_coada(t_coada& coada, int val) {
coada.elems[++coada.idx] = val;
}
int pop_coada(t_coada& coada) {
coada.idx--;
return coada.elems[coada.idx + 1];
}
bool is_empty_coada(t_coada& coada) {
return coada.idx == -1;
}
void dfs_coada(int nod, vector<int> graf[], bool viz[], t_coada& coada) {
viz[nod] = true;
push_coada(coada, nod);
for (int i = 0; i < graf[nod].size(); i++) {
int vecin = graf[nod][i];
if (!viz[vecin]) {
dfs_coada(vecin, graf, viz, coada);
}
}
}
void dfs_transpus(int nod, vector<int> graf[], bool viz[]) {
viz[nod] = true;
for (int i = 0; i < graf[nod].size(); i++) {
int vecin = graf[nod][i];
if (!viz[vecin]) {
dfs_transpus(vecin, graf, viz);
}
}
}
int main() {
int n, m;
vector<int> graf[MAX_N];
vector<int> graf_tran[MAX_N];
bool viz[MAX_N] = {0};
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int nod1, nod2;
fin >> nod1 >> nod2;
graf[nod1].push_back(nod2);
graf_tran[nod2].push_back(nod1);
}
t_coada coada;
init_coada(coada);
dfs_coada(1, graf, viz, coada);
for (int i = 1; i <= n; i++) {
viz[i] = false;
}
int cnt = 0;
while (!is_empty_coada(coada)) {
int nod = pop_coada(coada);
// fout << nod << endl;
if (!viz[nod]) {
cnt++;
dfs_transpus(nod, graf_tran, viz);
}
}
fout << cnt;
return 0;
}