Pagini recente » Cod sursa (job #2812878) | Cod sursa (job #1541721) | Cod sursa (job #1324301) | Cod sursa (job #1621973) | Cod sursa (job #1868988)
#include <bits/stdc++.h>
using namespace std;
vector <int> lst,comp;
vector <vector <int> > in,out,compt;
int n,m;
vector <bool> viz;
void DFS(int nod){
if(viz[nod]) return;
viz[nod]=true;
for(auto it: out[nod])
DFS(it);
lst.push_back(nod);
}
void Assign(int nod,int cmp){
if(comp[nod]) return;
comp[nod]=cmp;
compt.back().push_back(nod);
for(auto it: in[nod])
Assign(it,cmp);
}
int main()
{
int x,y;
ios_base::sync_with_stdio(false);
ifstream fin("sortaret.in");
fin>>n>>m;
in = vector < vector <int> > (n+1 , vector <int>());
out = vector <vector <int> > (n+1 , vector <int>());
viz = vector <bool> (n+1,0);
comp = vector <int> (n+1,0);
for(int i=1;i<=m;i++){
fin>>x>>y;
in[y].push_back(x);
out[x].push_back(y);
}
for(int i=1;i<=n;i++)
DFS(i);
int t=0;
for(int i=lst.size()-1;i>=0;i--)
{
if(comp[lst[i]]) continue;
compt.push_back(vector <int>());
Assign(lst[i],++t);
}
ofstream fout("sortaret.out");
for(int i=t-1;i>=0;i--)
{
for(auto it : compt[i])
fout<<it<<' ';
}
fout.close();
return 0;
}