首页 > 代码库 > ACM1258邻接表

ACM1258邻接表

2024-07-14 18:40:36   217人阅读

教训：使用邻接表的时候一定要把邻接表的结构组定义的足够大，不能仅仅等于节点的个数，因为线段的数量往往远超过节点的数量。

这个题目是拓扑排序练习，提高下理解。

 1 #include<iostream> 2 using namespace std; 3 struct TOPO 4 { 5     int from,to,next; 6 }; 7 TOPO p[200001];//这里要定义的足够大才行 8 int head[200001];//它和上面的是同步的大小才好 9 int *in,*use;10 int cnt;11 void Merge(int f,int t)12 {13     p[cnt].from=f;14     p[cnt].to=t;15     p[cnt].next=head[f];16     head[f]=cnt;17     cnt++;18 }19 int main()20 {21     int n,m;22     while(cin>>n>>m)23     {24         cnt=1;25         in=new int[n+1];26         use=new int[n+1];27         for(int i=0;i<=n;i++)28         {29             in[i]=0;30             use[i]=0;31             head[i]=-1;32         }33         int a,b;34         for(int i=1;i<=m;i++)35         {36             cin>>a>>b;37             Merge(a,b);38             in[b]++;39             //out[a]++;40         }41         int index=0;42         43         for(int i=1;i<=n;i++)44         {45             for(int j=1;j<=n;j++)46             {47                 if(!use[j]&&in[j]==0)48                 {49                     if(i>1)cout<<" ";50                     index=j;51                     use[j]=1;52                     cout<<j;53                     break;54                 }55             }56             for(int j=head[index];j!=-1;j=p[j].next)57             {58                 in[p[j].to]--;59             }60         }61         cout<<endl;62         delete []in;63         delete []use;64     }65     return 0;66 }

 


联系
我们