做完Victoria的舞会3，挑了vijos里强连通分量里面难度值最低的题目，也就是这道。先把第一小问做了，纯Tarjan，只是我学的时候的标程是用邻接表的，这题数据小于是用了邻接矩阵，两者之间的切换花了点时间，我天真地以为i<j等价于i的时间戳小于j的了，呵呵，那时候天真地连d数组都没写…

第二问看别人写了是用n次dfs？我多念了几遍题这**不就是明星奶牛么…感觉这两题基本都没什么差别。放假前老师给明星奶牛的评价是，做了这题图论基本复习了一遍…好吧，是啊，我把书翻出来，敲了一遍拓扑排序…

写完总觉得有点虚，觉得第二问的解法还有漏洞，我对于-1的唯一判断就是拓扑的时候有大于一个的出入度都为零的定点出现，不太清楚这个对不对…这题是不是改一改就能过明星奶牛了？

P.S. 好久没有码100行+的程序了，调试起来非常的虚。是我见识太狭隘还是代码风格太简洁还是做的都是水题？

P.S.2 题目描述里引用了《爱因为在心中》的歌词，挺喜欢这首歌的…~

P.S.3 不要理程序里的那个prim，一脑残忘记拓扑排序叫什么了，不是最小生成树…

program vijos_p1626;type ty=record          x,y:integer;        end;var map,map2:array[1..1000,1..1000] of word;    scc,low,s,w,d:array[0..1000] of integer;    v,sc:array[0..1000] of boolean;    jl:array[0..10000] of ty;    n,m,i,j,x,y,top,ans,t,ans2_0,ans_t:integer;procedure tarjan(u:integer);var i:integer;begin  v[u]:=true;  inc(top);s[top]:=u;sc[u]:=true;  inc(t);d[u]:=t;low[u]:=t;  for i:=1 to n do    if map[u,i]<>0 then      begin        if v[i]=false then          begin            tarjan(i);            if low[i]
      
       j) then        begin          inc(r[j]);          inc(c[i]);        end;  top:=0;  for i:=1 to n do    if (r[i]=0) and (scc[i]=i) then      begin        inc(top);        stack[top]:=i;        if c[i]=0 then          begin            writeln('-1');            halt;          end;      end;  while top>0 do    begin      now:=stack[top];dec(top);      if (c[now]=0) and (top<>0) then        begin          writeln('-1');          halt;        end;      for i:=1 to n do        if map2[now,i]=1 then          begin            dec(r[i]);            if r[i]=0 then              begin                inc(top);                stack[top]:=i;              end;          end;      if top=0 then        begin          ans2_0:=stack[1];          break;        end;    end;end;begin  readln(n,m);  for i:=1 to m do    begin      readln(jl[i].x,jl[i].y);      map[jl[i].x,jl[i].y]:=1;    end;  fillchar(v,sizeof(v),false);  fillchar(w,sizeof(w),0);  for i:=1 to n do    if v[i]=false then tarjan(i);  for i:=1 to n do    begin      inc(w[scc[i]]);      if w[scc[i]]=2 then inc(ans);      if w[scc[i]]=1 then inc(ans_T);    end;  writeln(ans);  if (ans=0) then    begin      writeln('-1');      halt;    end;  if (ans=1) and (ans_t=1) then ans2_0:=scc[1]  else    begin      for i:=1 to m do        map2[scc[jl[i].x],scc[jl[i].y]]:=1;   {
     xiao xin huan}      ans2_0:=-1;      prim;    end;  for i:=1 to n do    if scc[i]=ans2_0 then write(i,' ');end.
      

测试数据 #0: Accepted, time = 0 ms, mem = 4704 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 4704 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 4704 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 4704 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 4704 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 4704 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 4700 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 4700 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 4704 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 4700 KiB, score = 10

Accepted, time = 30 ms, mem = 4704 KiB, score = 100