Pagini recente » Cod sursa (job #1720865) | Cod sursa (job #38778) | Cod sursa (job #1751370) | Cod sursa (job #2741541) | Cod sursa (job #1155100)
#include <fstream>
#include <stack>
#include <vector>
#define MAX 100000
using namespace std;
int vect[MAX];
int out[MAX], k = 0;
vector<vector<int>> adiacenta;
vector<vector<int>> adiacentaInv;
stack<int> s;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfsRecInv(int v){
out[k++] = v+1;
vect[v] = 0;
for(int i = 0 ; i < adiacentaInv[v].size(); i++){
int x = adiacentaInv[v].at(i);
if(vect[x] != 0)
dfsRecInv(x);
}
}
void dfsRec(int v){
vect[v] = 1;
for(int i = 0 ; i < adiacenta[v].size(); i++){
int x = adiacenta[v].at(i);
if(vect[x] != 1)
dfsRec(x);
}
s.push(v);
}
void reverseG(){
for(int i = 0; i < adiacenta.size(); i++){
for(int j = 0; j < adiacenta[i].size(); j++){
adiacentaInv[adiacenta[i].at(j)].push_back(i);
}
}
}
void ctc(){
int x;
int count = 0;
while(s.size()){
x = s.top();
s.pop();
if(vect[x] != 0){
dfsRecInv(x);
k++;
count++;
}
}
fout << count << "\n";
}
int main(){
int n, m, a, b;
fin >> n >> m;
vector<int> v;
for(int i = 0; i < n; i++){
adiacenta.push_back(v);
adiacentaInv.push_back(v);
}
for(int i = 0; i < m; i++){
fin >> a >> b;
adiacenta[--a].push_back(--b);
}
for(int i = 0; i < n ; i++){
if(!vect[i]){
dfsRec(i);
}
}
reverseG();
ctc();
for(int i = 0 ; i < k; i++){
if(out[i] != 0){
fout << out[i] << " ";
}else{
fout << "\n";
}
}
return 0;
}