1 /*B*/
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 int head[
10010];
7 int indegree[
10010];
8 int mon[
10010];
9 int num,sum;
10 struct stu{
11 int to,next;
12 }edge[
20010];
13 void inin(){
//初始化
14 memset(indegree,
0,
sizeof(indegree));
15 memset(head,-
1,
sizeof(head));
16 memset(mon,
0,
sizeof(mon));
17 num=sum=
0;
18 }
19 void add(
int a,
int b){
//添加边
20 stu E=
{b,head[a]};
21 edge[num]=
E;
22 head[a]=num++
;
23 indegree[b]++
;
24 }
25 void topo(
int n){
26 int i,j,id,t,ans=
0;
27 queue<
int>
q;
28 while(!
q.empty()) q.pop();
29 for(i=
1;i<=n;i++
){
30 if(indegree[i]==
0){
31 q.push(i);
32 mon[i]=
888;
33 }
34 }
35 while(!
q.empty()){
36 t=
q.front();
37 q.pop();
38 indegree[t]=-
1;
39 sum+=
mon[t];
40 ans++
;
41 for(i=head[t];i!=-
1;i=
edge[i].next){
42 id=
edge[i].to;
43 if(--indegree[id]==
0){
44 mon[id]=mon[t]+
1;
45 q.push(id);
46 }
47 }
48 }
49 if(ans==n) printf(
"%d\n",sum);
50 else printf(
"-1\n");
51 }
52 int main(){
53 int n,m,i,j,a,b;
54 while(scanf(
"%d%d",&n,&m)!=
EOF){
55 inin();
56 for(i=
1;i<=m;i++
){
57 scanf(
"%d%d",&a,&
b);
58 add(b,a);
59 }
60 topo(n);
61 }
62 return 0;
63 }
64
65 /*C*/
66 /*注意要尽量让1考前，然后是2考前
67 例如
68 输入3 1 应该是3 1 2，如果是按普通的正向topu做的就是2 在最前面 即 2 3
69
70 1.
71 */
72 #include <cstdio>
73 #include <cstring>
74 #include <queue>
75 #define maxn 100002
76 using namespace std;
77
78 int head[maxn], indegree[maxn], ans[maxn];
79 struct Node{
80 int to, next;
81 } map[maxn];
82
83 void topoSort(
int n)
84 {
85 priority_queue<
int>
Q;
86 int i, u, id =
1;
87 for(i =
1; i <= n; ++
i)
88 if(!
indegree[i]) Q.push(i);
89 while(!Q.empty()){
//大的先弹出
90 ans[id++] = u =
Q.top();
91 Q.pop();
92 for(i = head[u]; i != -
1; i =
map[i].next)
93 if(!--
indegree[map[i].to]) Q.push(map[i].to);
94 }
95 for(i = n; i >=
1; --i)
//逆向输出
96 if(i !=
1) printf(
"%d ", ans[i]);
97 else printf(
"%d\n", ans[i]);
98 }
99
100 int main()
101 {
102 int t, n, m, a, b, i;
103 scanf(
"%d", &
t);
104 while(t--
){
105 memset(indegree,
0,
sizeof(indegree));
106 memset(head, -
1,
sizeof(head));
107 scanf(
"%d%d", &n, &
m);
108 for(i =
0; i < m; ++
i){
109 scanf(
"%d%d", &a, &
b);
110 map[i].to =
a;
111 map[i].next =
head[b];
112 head[b] =
i;
113 ++
indegree[a];
114 }
115 topoSort(n);
116 }
117 return 0;
118 }
119
120 /*D*/
121 #include<cstdio>
122 #include<cstring>
123 #include<queue>
124 using namespace std;
125 int head[
10010];
126 int per[
10010];
127 int indegree[
10010];
128 int num;
129 struct stu{
130 int to,next;
131 }edge[
20010];
132 struct node{
133 int a;
134 char s[
2];
135 int b;
136 }tol[
20010];
137 void inin(
int n){
138 memset(head,-
1,
sizeof(head));
139 memset(indegree,
0,
sizeof(indegree));
140 num=
0;
141 for(
int i=
0;i<=n;i++
)
142 per[i]=
i;
143 }
144 int find(
int x){
145 return per[x]=x==per[x]?
x:find(per[x]);
146 }
147 void judge(
int x,
int y){
148 int fx=
find(x);
149 int fy=
find(y);
150 if(per[fx]!=
per[fy]){
151 per[fx]=
fy;
152 }
153 }
154 void add(
int a,
int b){
//添加边
155 stu E=
{b,head[a]};
156 edge[num]=
E;
157 head[a]=num++
;
158 indegree[b]++
;
159 }
160 void topo(
int n){
161 int i,j,k,l,flag1,flag2,sum;
//sum表示独立的点
162 l=k=flag1=flag2=sum=
0;
//flag1表示条件不够，flag2表示矛盾
163 queue<
int>
q;
164 while(!
q.empty()) q.pop();
165 for(i=
0;i<n;i++
){
166 if(i==
per[i]){
167 sum++
;
168 if(indegree[i]==
0){
169 q.push(i);
170 k++
;
171 }
172 }
173 }
174 if(k>
1) flag1=
1;
175 while(!
q.empty()){
176 int v=
q.front();
177 q.pop();
178 l++
;
179 k=
0;
180 for(i=head[v];i!=-
1;i=
edge[i].next){
181 int w=
edge[i].to;
182 indegree[w]--
;
183 if(indegree[w]==
0){
184 q.push(w);
185 k++
;
186 }
187 }
188 if(k>
1){
189 flag1=
1;
190 }
191 }
192 if(l!=sum) flag2=
1;
193 if(flag1&&
flag2){
194 printf(
"CONFLICT\n");
195 }
196 else if(flag1){
197 printf(
"UNCERTAIN\n");
198 }
199 else if(flag2){
200 printf(
"CONFLICT\n");
201 }
202 else{
203 printf(
"OK\n");
204 }
205
206 }
207 int main(){
208 int n,m,i,j,a,b;
209 char s[
2];
210 while(scanf(
"%d%d",&n,&m)!=
EOF){
211 inin(n);
212 for(i=
0;i<m;i++){
//为了合并==的元素
213 scanf(
"%d%s%d",&tol[i].a,tol[i].s,&
tol[i].b);
214 if(tol[i].s[
0]==
'='){
215 judge(tol[i].a,tol[i].b);
216 }
217 }
218 for(i=
0;i<m;i++
){
219 if(tol[i].s[
0]==
'=')
continue;
220 int a=find(tol[i].a);
//之后保证全都是祖先元素操作
221 int b=
find(tol[i].b);
222 if(tol[i].s[
0]==
'>'){
223 add(a,b);
224 }
225 else{
226 add(b,a);
227 }
228 }
229 topo(n);
230 }
231 return 0;
232 }
233
234
235 /*E*/
236 #include<cstdio>
237 #include<cstring>
238 #include<iostream>
239 using namespace std;
240 int map[
15][
15];
241 int indegree[
12];
242 int dir[
4][
2]= {
0,
0,
1,
0,
0,
1,
1,
1};
//方向数组
243 int local[
10][
2]= {-
1,-
1,
0,
0,
0,
1,
0,
2,
1,
0,
1,
1,
1,
2,
2,
0,
2,
1,
2,
2};
244
245 // 1~9号窗口的固定位置
246 int screen[
5][
5];
247 void inin(){
248 memset(map,
0,
sizeof(map));
249 memset(indegree,
0,
sizeof(indegree));
250 }
251 int topo()
252 {
253 int i,j,id,flag;
254 for(i=
1; i<=
9; i++
)
255 {
256 flag=
0;
257 for(j=
1; j<=
9; j++
)
258 if(indegree[j]==
0)
259 {
260 flag=
1;
261 id=
j;
262 break;
263 }
264 if(flag==
0)
265 return 0;
266 indegree[id]=-
1;
267 for(j=
1; j<=
9; j++
)
268 if(map[id][j])
269 indegree[j]--
;
270 }
271 return 1;
272 }
273 int main()
274 {
275 char s[
15];
276 int i,j,k;
277 int x,y,z;
278 while(scanf(
"%s",s)&&strcmp(s,
"ENDOFINPUT")!=
0)
279 {
280 inin();
281 for(i=
0; i<
4; i++
)
282 for(j=
0; j<
4; j++
)
283 scanf(
"%d",&
screen[i][j]);
284 scanf(
"%s",s);
285 for(k=
1; k<=
9; k++
)
286 {
287 for(i=
0; i<
4; i++
)
288 {
289 x=local[k][
0]+dir[i][
0];
290 y=local[k][
1]+dir[i][
1];
291 z=
screen[x][y];
292 if(z!=k&&!
map[k][z])
293 {
294 map[k][z]=
1;
295 indegree[z]++
;
296 }
297 }
298 }
299 if(topo())
300 printf(
"THESE WINDOWS ARE CLEAN\n");
301 else
302 printf(
"THESE WINDOWS ARE BROKEN\n");
303 }
304 return 0;
305 }
306
307
308 /*F*/
309 #include<cstdio>
310 #include<cstring>
311 int map[
110][
110];
312 int indegree[
110];
313 void inin(){
314 memset(map,
0,
sizeof(map));
315 memset(indegree,
0,
sizeof(indegree));
316 }
317 void topo(
int n)
318 {
319 int i,j,m,t=
0;
320 int queue[
110];
321 for(j=
1;j<=n;j++
){
322 for(i=
1;i<=n;i++
){
323 if(indegree[i]==
0){
//找出前驱数量为零的的点即每次找到第一名
324 m=i;
break;
325 }
326 }
327 queue[t++]=m;indegree[m]=-
1;
//将第一名的前驱数量设为-1
328 for(i=
1;i<=n;++i){
//第二步将前驱中含有第一名的点前驱数量减1
329 if(map[m][i])indegree[i]--
;
330 }
331 }
332 for(i=
0;i<n;++
i){
333 printf(
"%d ",queue[i]);
334 }
335 printf(
"\n");
336 }
337 int main(){
338 int n,i,p;
339 while(scanf(
"%d",&n)!=
EOF){
340 inin();
341 for(i=
1;i<=n;i++
){
342 while(scanf(
"%d",&
p),p){
343 map[i][p]=
1;
344 indegree[p]++
;
345 }
346 }
347 topo(n);
348 }
349 return 0;
350 }
View Code
/*hdu1285--采用二维数组记录两者之间的关系*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int map[510][510];//前驱数量
int indegree[510];
int queue[510];//保存拓扑序列
void topo(int n)
{
int i,j,m,t=0;
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if(indegree[i]==0) //找出前驱数量为零的的点即每次找到第一名
{
m=i;break;
}
}
queue[t++]=m;indegree[m]=-1;//将第一名的前驱数量设为-1
for(i=1;i<=n;++i)//第二步将前驱中含有第一名的点前驱数量减1
{
if(map[m][i])indegree[i]--;
}
}
printf("%d",queue[0]);//输出拓扑序列
for(i=1;i<n;++i)
{
printf(" %d",queue[i]);
}
printf("\n");
}
int main()
{
int n,m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,0,sizeof(indegree));//初始化
memset(map,0,sizeof(map));
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
if(map[a][b]==0)//避免重复的数据输入
{
map[a][b]=1;indegree[b]++;//第一步记录关系和点的前驱数量
}
}
topo(n);//调用拓扑排序
}
return 0;
}
/*hdu1285--采用邻接表记录两者之间的关系*/
#include<cstdio>
#include<cstring>
int head[510];
int indegree[510];
int queue[510];
int num;
struct stu{
int to,next;
}edge[2510];
void inin(){//初始化
memset(indegree,0,sizeof(indegree));
memset(head,-1,sizeof(head));
num=0;
}
void add(int a,int b){//添加边
stu E={b,head[a]};
edge[num]=E;
head[a]=num++;
indegree[b]++;
}
void topo(int n){
int i,j,id,t=0;
for(j=1;j<=n;j++){
for(i=1;i<=n;i++){
if(indegree[i]==0){
id=i;
break;
}
}
queue[t++]=id;indegree[id]=-1;
for(i=head[id];i!=-1;i=edge[i].next){
int k=edge[i].to;
indegree[k]--;
}
}
printf("%d",queue[0]);//输出拓扑序列
for(i=1;i<n;++i){
printf(" %d",queue[i]);
}
printf("\n");
}
int main(){
int n,m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF){
inin();
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
add(a,b);
}
topo(n);
}
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include <functional>
using namespace std;
int map[510][510];
int indegree[510];
void topo(int n)
{
int i,j,m,t=0;
priority_queue<int,vector<int>,greater<int> >Q;//按从小到大顺序输出队
for(i=1;i<=n;i++){
if(indegree[i]==0){
Q.push(i);
}
}
int sign=1;
while(!Q.empty()){
int top=Q.top();
Q.pop();
indegree[top]=-1;
if(sign)
printf("%d",top);
else
printf(" %d",top);
sign=0;
for(i=1;i<=n;i++){
if(map[top][i]){
indegree[i]--;
if(indegree[i]==0){
Q.push(i);
}
}
}
}
printf("\n");
}
int main()
{
int n,m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF){
memset(indegree,0,sizeof(indegree));
memset(map,0,sizeof(map));
for(i=0;i<m;++i){
scanf("%d%d",&a,&b);
if(map[a][b]==0){
map[a][b]=1;indegree[b]++;
}
}
topo(n);
}
return 0;
}
转载于:https://www.cnblogs.com/llal/p/5740730.html
