Pagini recente » Cod sursa (job #579516) | Cod sursa (job #1871870) | Cod sursa (job #2729963) | Cod sursa (job #2451513) | Cod sursa (job #2970823)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> st;
int pos = -1;
void dfs_1(int s, vector<int>& vizitat, vector<vector<int>>& adj, stack<int>& st) {
vizitat[s] = 1;
for(auto& vecin: adj[s]) {
if(vizitat[vecin] == 0)
dfs_1(vecin, vizitat, adj, st);
}
st.push(s);
}
void dfs_2 (int s, vector<int>& vizitat_tr, vector<vector<int>>& adj_tr, vector<int>& componente) {
pos++;
vizitat_tr[s] = 1;
componente[pos] = s;
for(auto vecin: adj_tr[s]) {
if(vizitat_tr[vecin] == 0) {
dfs_2(vecin, vizitat_tr, adj_tr, componente);
}
}
}
int main()
{
int n, m, ctc = 0;
fin>>n>>m;
vector<vector<int>> adj(n + 1);
vector<vector<int>> adj_tr(n + 1);
vector<int> vizitat(n + 1);
vector<int> vizitat_tr(n + 1);
vector<int> componente(2*n);
for (int i = 0; i < m; i++) {
int a, b;
fin>>a>>b;
adj[a].push_back(b);
adj_tr[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
vizitat[i] = 0;
vizitat_tr[i] = 0;
}
for (int i = 1; i <= n; i++)
if(vizitat[i] == 0)
dfs_1(i, vizitat, adj, st);
while(!st.empty()) {
int i = st.top();
st.pop();
if (vizitat_tr[i] == 0) {
dfs_2(i, vizitat_tr, adj_tr, componente);
pos++;
ctc++;
componente[pos] = -1;
}
}
componente.resize(n + ctc);
fout<<ctc<<endl;
for(auto& a: componente) {
if(a != -1)
fout<<a<<" ";
else
fout<<"\n";
}
return 0;
}