Pagini recente » Cod sursa (job #2911581) | Cod sursa (job #231417) | Cod sursa (job #329207) | Cod sursa (job #20254) | Cod sursa (job #2579614)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::queue;
using std::stack;
using std::fstream;
using std::ios;
using std::sort;
fstream file1("ctc.in", ios::in);
fstream file2("ctc.out", ios::out);
int nr_noduri, nr_muchii, count;
vector<int> vecini[100005], vecini_inv[100005], sol[100005];
vector<bool> vizitat(100005), vizitat_inv(100005);
stack<int> stiva;
void form_vecini();
void f();
void dfs(int start);
void dfs_t(int start);
int main(int argc, char** argv) {
file1 >> nr_noduri >> nr_muchii;
form_vecini();
f();
file2 << count << endl;
for (int i{ 0 }; i < count; i++) {
for (int j{ 0 }; j < sol[i].size(); j++) {
file2 << sol[i][j] << ' ';
}
file2 << endl;
}
file1.close();
file2.close();
return 0;
}
void f() {
for (int i{ 1 }; i <= nr_noduri; i++) {
if (!vizitat[i]) {
dfs(i);
}
}
while (!stiva.empty()) {
int nod = stiva.top();
if (!vizitat_inv[nod]) {
dfs_t(nod);
count++;
}
stiva.pop();
}
}
void dfs_t(int start) {
vizitat_inv[start] = true;
for (auto it = vecini_inv[start].begin(); it != vecini_inv[start].end(); it++) {
if (!vizitat_inv[*it]) {
vizitat_inv[*it] = true;
dfs_t(*it);
}
}
sol[count].push_back(start);
}
void dfs(int start) {
vizitat[start] = true;
for (auto it = vecini[start].begin(); it != vecini[start].end(); it++) {
if (!vizitat[*it]) {
vizitat[*it] = true;
dfs(*it);
}
}
stiva.push(start);
}
void form_vecini() {
int i, j;
while (file1 >> i >> j) {
vecini[i].push_back(j);
vecini_inv[j].push_back(i);
}
}