Pagini recente » Cod sursa (job #1084665) | Cod sursa (job #1001016) | Cod sursa (job #2928193) | Cod sursa (job #341996) | Cod sursa (job #2927635)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void firstDFS(int node, vector<int> *adjacencyList, bool *isVisited, stack<int> *stack) {
isVisited[node] = true;
for (auto adjacentNode : adjacencyList[node])
if (not isVisited[node])
firstDFS(adjacentNode, adjacencyList, isVisited, stack);
stack->push(node);
}
void secondDFS(int node, vector<int> *adjacencyList, bool *isVisited, string *toBeWritten) {
isVisited[node] = true;
for (auto adjacentNode : adjacencyList[node])
if (not isVisited[node])
secondDFS(adjacentNode, adjacencyList, isVisited, toBeWritten);
*toBeWritten = *toBeWritten + " " + to_string(node);
}
void writeSCCs(int numberOfNodes, vector<int> *adjacencyList) {
bool isVisited[numberOfNodes];
for (int node=0; node<numberOfNodes; node++)
isVisited[node] = false;
stack<int> topologicalOrderingOfSCCs;
// first DFS, used to find the topological ordering of the underlying graph's SCCs
for (int node=0; node<numberOfNodes; node++)
if (not isVisited[node])
firstDFS(node, adjacencyList, isVisited, &topologicalOrderingOfSCCs);
// marking all nodes as not visited, in preparation for the second DFS
for (int node=0; node<numberOfNodes; node++)
isVisited[node] = false;
vector<int> transposedAdjacencyList[numberOfNodes]; // needed to store the adjacency list of the transposed graph
// storing the adjacency list of the transposed graph
for (int node=0; node<numberOfNodes; node++)
for (auto adjacentNode : adjacencyList[node])
transposedAdjacencyList[adjacentNode].push_back(node);
string toBeWritten;
int numberOfSCCs = 0;
// second DFS, used to find SCCs (in reverse-topological order of the transposed graph's SCCs)
while (not topologicalOrderingOfSCCs.empty()) {
if (not isVisited[topologicalOrderingOfSCCs.top()]) {
secondDFS(topologicalOrderingOfSCCs.top(), transposedAdjacencyList, isVisited, &toBeWritten);
numberOfSCCs++;
toBeWritten = toBeWritten + "\n";
}
topologicalOrderingOfSCCs.pop();
}
ofstream output("ctc.out");
output<<numberOfSCCs<<'\n'<<toBeWritten;
}
int main() {
int numberOfNodes, numberOfEdges, outNode, inNode;
ifstream input("ctc.in");
input>>numberOfNodes>>numberOfEdges;
vector<int> adjacencyList[numberOfNodes];
for(int i=0; i<numberOfEdges; i++) {
input>>outNode>>inNode;
adjacencyList[outNode-1].push_back(inNode-1);
}
writeSCCs(numberOfNodes, adjacencyList);
return 0;
}