Pagini recente » Borderou de evaluare (job #200859) | Borderou de evaluare (job #1014563) | Borderou de evaluare (job #2447783) | Borderou de evaluare (job #2944657) | Cod sursa (job #3274126)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("ceva.in");
ofstream fout("ceva.out");
void DFS1(int node, vector<bool> &isVisited, vector<int> &topSort, vector<vector<int>> &graph) {
isVisited[node] = true;
for(auto neighbor : graph[node]) {
if(!isVisited[neighbor])
DFS1(neighbor, isVisited, topSort, graph);
}
topSort.push_back(node);
}
void DFS2(int node, int parent, vector<int> &rep, vector<bool> &isVisited, vector<set<int>> &components, vector<vector<int>> &rgraph) {
isVisited[node] = true;
rep[node] = parent;
components[parent].insert(node);
for(auto neighbor : rgraph[node]) {
if(!isVisited[neighbor])
DFS2(neighbor, parent, rep, isVisited, components, rgraph);
}
}
int main() {
int noNodes, noEdges;
fin >> noNodes >> noEdges;
vector<vector<int>> graph(noNodes+1, vector<int>());
vector<vector<int>> rgraph(noNodes+1, vector<int>());
vector<set<int>> components(noNodes+1, set<int>());
for(int i=1; i<=noEdges; i++) {
int firstNode, secondNode;
fin >> firstNode >> secondNode;
graph[firstNode].push_back(secondNode);
rgraph[secondNode].push_back(firstNode);
}
vector<int> topSort;
vector<bool> isVisited(noNodes+1, false);
for(int i=1; i<=noNodes; i++) {
if(!isVisited[i])
DFS1(i, isVisited, topSort, graph);
}
reverse(topSort.begin(), topSort.end());
fill(isVisited.begin(), isVisited.end(), false);
vector<int> rep(noNodes+1, -1);
int compTari = 1;
for(auto node : topSort) {
if(!isVisited[node]) {
DFS2(node, compTari++, rep, isVisited, components, rgraph);
}
}
fout << compTari-1 << '\n';
for(int i=1; i<compTari; i++) {
for(auto node : components[i])
fout << node << ' ';
fout << '\n';
}
return 0;
}