Pagini recente » Cod sursa (job #2348214) | Cod sursa (job #378654) | Cod sursa (job #2915559) | Cod sursa (job #757747) | Cod sursa (job #2925473)
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
stack<int> s;
vector<vector<int>> adj, adjt, components;
vector<bool> viz;
vector<int> currComponent;
void dfs(int node) {
viz[node] = true;
for(auto nextNode : adj[node])
if(!viz[nextNode])
dfs(nextNode);
s.push(node);
}
void showComponent(int node) {
viz[node] = false;
currComponent.push_back(node);
for(auto nextNode : adjt[node])
if(viz[nextNode])
showComponent(nextNode);
}
int main() {
int n, m, x, y;
in >> n >> m;
adj.resize(n + 1);
adjt.resize(n + 1);
viz.resize(n + 1, false);
while(m --) {
in >> x >> y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
for(int i = 1; i <= n; ++ i)
if(!viz[i])
dfs(i);
// pentru a nu mai seta toate elementele lui viz la false, de acum inainte o sa folosesc pe dos acest vector
// i.e. daca un nod este vizitat in timpul lui showComponent(), el va fi marcat cu false in viz
while(!s.empty()) {
if(viz[s.top()]) {
showComponent(s.top());
s.pop();
components.push_back(currComponent);
currComponent.clear();
}
else
s.pop();
}
out << components.size() << '\n';
for(auto comp : components){
for(auto node : comp)
out << node << ' ';
out << '\n';
}
return 0;
}