Pagini recente » Cod sursa (job #1997960) | Cod sursa (job #1235442) | Cod sursa (job #2366897) | Cod sursa (job #1207370) | Cod sursa (job #2928807)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int>> graph;
vector<vector<int>> graph_t;
int index=1;
stack <int> S;
queue <int> Q;
vector<int> visited;
void DFS_t(vector<vector<int>> graph_t, int n, int x, int index){
visited[x]=index;
for(int i = 0; i < graph_t[x].size(); i ++){
if(visited[graph_t[x][i]] == 0){
DFS_t(graph_t, n, graph_t[x][i], index);
}
}
S.push(x);
}
void DFS(vector<vector<int>> graph, int n, int x){
visited[x] = index;
for(int i = 0; i < graph[x].size(); i ++){
if(visited[graph[x][i]] == 0){
DFS(graph, n, graph[x][i]);
}
}
S.push(x);
}
int main() {
int n, m;
f >> n >> m;
graph.resize(n+1);
graph_t.resize(n+1);
visited.resize(n+1);
for(int i = 0; i < m; i ++){
int x, y;
f >> x >> y;
graph[x].push_back(y);
graph_t[y].push_back(x);
}
for(int i = 1; i <= n;i ++){
if(visited[i] == 0){
DFS(graph, n, i);
}
}
for(int i = 1; i <= n; i ++){
visited[i] = 0;
}
while(!S.empty()){
int x=S.top();
S.pop();
if(visited[x] == 0){
DFS_t(graph_t, n, x, index);
for(int i = 1; i <= n; i++){
if(visited[i] == index){
Q.push(i);
}
}
Q.push(-1);
index += 1;
}
}
g << index - 1 << endl;
while(!Q.empty()){
int x=Q.front();
Q.pop();
if (x != -1)
g << x << " ";
else
g << endl;
}
return 0;
}