传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=1042
试题描述：
LZJ有一个问题想问问大家。他在写函数时有时候很头疼,如他写了这样几个函数:
void f1()
{
f2();
f3();
}
void f2()
{
f3();
}
void f3()
{
f1();
}
LZJ发现他无论怎么调换函数的位置，编译器总是不能通过编译，因为编译器规定调用的函数必须在当前函数之前写。
还有一种情况是这样的：
void f4()
{
f4();
}
虽然能通过编译但会无限递归。
现在LZJ想问问你，他写了一些函数，并且给你每个函数调用了哪些别的函数（可能调用本身），请问他能否通过调整函数的位置，使得编译器通过编译且不会出现无限递归？
输入：
输入第一行为一个正整数N，表示有N个函数。
接下来N行每第i行开始有一个自然数K，表示第i个函数共调用了多少别的函数（可能调用本身）,接下来K个正整数vij，表示函数i调用了函数vij。
输出：
若可以输出“Yes”,否则输出“No”。
输入示例：
5
1 2
1 3
2 4 5
1 5
0
输出示例：
Yes
其他说明：
1<=N<=200，1<=K<=N, 1<=vij<=N
题解：裸有向图判环直接拓扑排序，然后如果作死可以把边搞成负的上Bellman_Ford……
然后记得判自环。
拓扑排序：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#define REP(s, n) for(int i = s; i <= n; i ++)
using namespace std;
const int maxn = + ;
const int maxm = + ;
int In[maxn], n, cnt = ;
int first[maxn], next[maxm], to[maxm];
bool vis[maxn], TAT = true;
int ms = ;
void AddEdge(int u, int v){
next[ms] = first[u];
first[u] = ms;
to[ms] = v;
In[v] ++; ms ++;
return ;
}
void read(int& x){
x = ; int sig = ; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') sig = -; ch = getchar(); }
while(isdigit(ch)) x = * x + ch -'', ch = getchar();
x *= sig; return ;
}
queue<int> Q;
void init(){
read(n);
int temp;
REP(, n){
read(cnt);
while(cnt --){
read(temp);
if(temp == i) { TAT = false; return ; }
AddEdge(i, temp);
}
}
return ;
}
void work(){
if(!TAT) return ;
REP(, n) if(In[i] == ) Q.push(i), vis[i] = true;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = first[x]; i; i = next[i]){
int& v = to[i];
if(vis[v]) continue;
In[v] --;
if(In[v] == ) Q.push(v), vis[v] = true;
}
}
return ;
}
void print(){
if(!TAT) { puts("No"); return ;}
REP(, n) if(!vis[i]) { puts("No"); return ;}
puts("Yes"); return ;
}
int main(){
init();
work();
print();
return ;
}
Bellman_Ford：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 1000000000
using namespace std;
const int maxn=+,maxm=+;
struct Tedge{int x,y,w,next;}adj[maxm];int ms=,fch[maxn];
void AddEdge(int u,int v){
adj[++ms]=(Tedge){u,v,-,fch[u]};fch[u]=ms;return;
}
int d[maxn],n;
bool relax(int u,int v,int w){
if(d[v]>d[u]+w){d[v]=d[u]+w;return true;}
return false;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){ }
bool bellman_ford(){
n=read();
for(int i=;i<=n;i++) d[i]=INF;
for(int i=;i<=n;i++){
int k=read();
for(int j=;j<k;j++){
int a=read();
if(i==a) return false;
AddEdge(i,a);
}
}
bool ToT;
for(int i=;i<=n;i++){
ToT=false;
for(int i=;i<=ms;i++){
int u=adj[i].x,v=adj[i].y,w=adj[i].w;
if(relax(u,v,w)) ToT=true;
}
if(!ToT) break;
}
for(int i=;i<=ms;i++){
int u=adj[i].x,v=adj[i].y,w=adj[i].w;
if(relax(u,v,w)) return false;
}
return true;
}
void work(){
if(bellman_ford()) puts("Yes");
else puts("No");
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}
/*
5
1 1
1 3
1 4
1 5
1 6
*/
Spfa：超级点向所有点引0再跑
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define inf 100000000
using namespace std;
const int maxn=+,maxm=+;
struct Tedge{int x,y,w,next;}adj[maxm];int ms=,fch[maxn];
void AddEdge(int u,int v,int w){adj[++ms]=(Tedge){u,v,w,fch[u]};fch[u]=ms;return;}
int n;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;} if(x<) putchar('-'),x=-x;
int len=,buf[]; while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
bool inque[maxn];
int d[maxn],cnt[maxn];
bool SPFA(int S){
for(int i=;i<=n+;i++) d[i]=inf;
queue<int>Q;Q.push(S);inque[S]=true;d[S]=;
while(!Q.empty()){
int u=Q.front();Q.pop();inque[u]=false;
for(int i=fch[u];i;i=adj[i].next){
int v=adj[i].y;
if(d[v]>d[u]+adj[i].w){
d[v]=d[u]+adj[i].w;
if(!inque[v]){
if(++cnt[v]>=n+) return false;
inque[v]=true;
Q.push(v);
}
}
}
}return true;
}
void init(){
n=read();
for(int i=;i<=n;i++){
AddEdge(n+,i,);
int tp=read();
for(int j=;j<=tp;j++){
int v=read();
if(v==i){puts("No");return;}
AddEdge(i,v,-);
}
}
//for(int i=1;i<=ms;i++) printf("%d %d %d\n",adj[i].x,adj[i].y,adj[i].w);
if(SPFA(n+)) puts("Yes");
else puts("No");
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}