Pagini recente » Cod sursa (job #261554) | Cod sursa (job #315997) | Cod sursa (job #1471850) | Cod sursa (job #110671) | Cod sursa (job #2374054)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
struct IT
{
int x,y;
}temp;
stack<int>st;
int n,m,i,j,k,viz[105];
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
int ttime,dfsRoot,rootChildren;
vector< vector<int> > sol;
void Add(int tt, int fiu) {
vector<int> step;
while (st.top() != fiu) {
step.push_back(st.top());
st.pop();
}
step.push_back(fiu);
step.push_back(tt);
st.pop();
sol.push_back(step);
}
void dfs(int u)
{
int j;
viz[u]=1;
for(j=0;j<G[u].size();j++)
if(viz[G[u][j]]==0)
dfs(G[u][j]);
st.push(u);
}
/*
void articulationPoint(int u)
{
int v;
ttime++;
dfs_discover[u]=dfs_low[u]=ttime;
for(int j=0;j<G[u].size();j++)
{
v=G[u][j];
if(!dfs_discover[v])
{
dfs_parent[v]=u;
if(u==dfsRoot)rootChildren++;
temp.x=u;
temp.y=v;
st.push(v);
articulationPoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=1;
Add(u,v);
}
dfs_low[u]=min(dfs_low[u],dfs_low[v]);
}
else
{
if(dfs_parent[u]!=v)
dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
}
}
}
*/
int main()
{
int u,v;
fin>>n>>m;
// for(j=1;j<=101;j++)viz[j]=0;
for(i=1;i<=m;i++)
{
fin>>u>>v;
G[u].push_back(v);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
dfs(i);
while(!st.empty())
{
fout<<st.top()<<" ";
st.pop();
}
/*
dfs_parent.assign(n+1,0);
articulation_vertex.assign(n+1,0);
dfs_discover.assign(n+1,0);
dfs_low.assign(n+1,0);
for(i=1;i<=n;i++)
{
if(dfs_discover[i]==0)
{
dfsRoot=i;
rootChildren=0;
articulationPoint(i);
articulation_vertex[dfsRoot]=rootChildren>1;
}
}
fout<<sol.size()<<endl;
for (int i = 0; i <sol.size(); i++)
sort(sol[i].begin(),sol[i].end());
for (int i = 0; i <sol.size(); i++)
{
for(j=0;j<sol[i].size();j++)
fout<<sol[i][j]<<" ";
fout<<"\n";
}*/
return 0;
}