Pagini recente » Cod sursa (job #855228) | Cod sursa (job #2548878) | Istoria paginii runda/oji_bv_2022/clasament | Cod sursa (job #709114) | Cod sursa (job #2928192)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>* adjListG;
vector<int>* adjListGT;
bool* visited;
stack<int> nodes;
std::stringstream ssResult;
void DFS(int currentNode) {
//cout << currentNode << " ";
visited[currentNode] = true;
for(int i = 0; i<adjListG[currentNode].size(); i++) {
if(!visited[adjListG[currentNode][i]]) {
DFS(adjListG[currentNode][i]);
}
}
nodes.push(currentNode);
}
void DFST(int currentNode) {
ssResult << currentNode << " ";
visited[currentNode] = true;
for(int i = 0; i<adjListGT[currentNode].size(); i++) {
if(!visited[adjListGT[currentNode][i]]) {
DFST(adjListGT[currentNode][i]);
}
}
}
int main() {
int N, M, x, y;
fin >> N >> M;
adjListG = new vector<int>[N+1];
adjListGT = new vector<int>[N+1];
visited = new bool[N+1];
for(int i = 0; i<N;i++) {
visited[i] = false;
}
for(int i = 0; i<M;++i) {
fin >> x >> y;
adjListG[x].push_back(y);
adjListGT[y].push_back(x);
}
// Print adj list
// for(int i = 1; i<=N; i++) {
// for(int j = 0; j < adjListG[i].size(); j++) {
// cout << adjListG[i][j] << " ";
// }
// cout << "\n";
// }
for(int i = 1; i <= N; i++) {
if(!visited[i]) {
DFS(i);
}
}
for(int i = 0; i<=N;i++) {
visited[i] = false;
}
// cout << "\n---\n";
// for(int i = 0; i<N;i++) {
// cout << visited[i] << " ";
// }
// cout << "\n---\n";
int nrComp = 0;
while(!nodes.empty()) {
int currentNode = nodes.top();
nodes.pop();
if(!visited[currentNode]) {
DFST(currentNode);
++nrComp;
ssResult << "\n";
}
}
fout << nrComp << "\n";
fout << ssResult.rdbuf();
return 0;
}