Pagini recente » Cod sursa (job #1807323) | Cod sursa (job #1061951) | Cod sursa (job #2503960) | Cod sursa (job #2955916) | Cod sursa (job #2932654)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
#define N 100001
vector<int> graph[N], graphT[N], solution[N];
bool viz[N];
deque<int> deq;
deque<int> :: reverse_iterator it;
int ctc;
void topo(int node) {
viz[node] = 1; //frecventa o fac sa verific nodurile inserate in coada
for (int i = 0; i < graph[node].size(); ++i) {
if (!viz[graph[node][i]]) {
topo(graph[node][i]);
}
}
deq.push_back(node);
}
void dfs(int node) {
viz[node]= 1;
solution[ctc].push_back(node);
for (int i = 0; i < graphT[node].size(); ++i) {
if (!viz[graphT[node][i]]) {
dfs(graphT[node][i]);
}
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
int nodes, arcs, a, b;
f >> nodes >> arcs;
for (int i = 1; i <= arcs; ++i) {
f >> a >> b;
graph[a].push_back(b);
graphT[b].push_back(a);
}
for (int i = 1; i <= nodes; ++i) {
if (!viz[i]) {
topo(i);
}
}
for (int i = 1; i <= nodes; ++i) {
viz[i] = 0;
}
for (it = deq.rbegin(); it != deq.rend(); ++it) {
int value = *it;
if (!viz[value]) {
++ctc;
dfs(value);
}
}
g << ctc << "\n";
for (int i = 1; i <= ctc; ++i) {
while (!solution[i].empty()) {
g << solution[i].back() << " ";
solution[i].pop_back();
}
g << "\n";
}
f.close();
g.close();
return 0;
}