T1:

题目：给定一个n个节点的图，每个节点只有一条入边。从每个点开始找来的点，问第一次遍历过两次的点是哪个。(n=1000) 思路：暴力，打标记即可。

/*
n=1000,对于每个人，跑一遍DFS即可。 
*/ 
#include<bits/stdc++.h>
using namespace std;
int n;
int p[10005];
int vis[10005];
bool flag=1;
void DFS(int x){
	vis[x]++;	
	if(vis[x]>=2){if(flag)cout<<x<<" ";flag=0;return;}
    if(!flag)return;
	DFS(p[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	for(int i=1;i<=n;i++){
		// vis[i]=1;
		DFS(i);
		for(int j=1;j<=n;j++){
			vis[j]=0;
		}
        flag=1;
	}
	return 0; 
} 

T2:

题目：每种药剂由其他药剂合成。共有n中药剂。c[i]表示第i种药剂的花费。有一些药剂不用花钱了。问拥有各个药剂所需要的钱。

分析：take[i]=min(合成（所有前驱），c[i])

思路：记忆化搜索。

#include<bits/stdc++.h>
using namespace std;
long long ans[200005];
int n,k;
int c[200005]; 
int out[200005];
int in[200005];
vector<int>G1[200005];
vector<int>G2[200005];
int dfs(int x){
	if(in[x]==0){
		if(ans[x]==0x3f3f3f3f)ans[x]=c[x];
		return ans[x];
	}
	if(ans[x]==0x3f3f3f3f){
		ans[x]=0;
		for(int i=0;i<G2[x].size();i++){
			ans[x]+=dfs(G2[x][i]);
		}
	}
    ans[x]=min(ans[x],(long long)c[x]);
	return ans[x];
}
int main(){
int T;
cin>>T;
while(T--){

	cin>>n>>k;
    for(int i=1;i<=n;i++){
        G1[i].clear();
        G2[i].clear();
        in[i]=0;
        out[i]=0;
        ans[i]=0x3f3f3f3f;
    }
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	for(int i=1;i<=k;i++){int x;cin>>x;c[x]=0;}
	for(int i=1;i<=n;i++){
		int m;
		scanf("%d",&m);
		if(m==0){
			ans[i]=c[i]; 
		}
		in[i]+=m;
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);
			out[x]++;
			G2[i].push_back(x);
		}
	} 
	for(int i=1;i<=n;i++){
		if(out[i]==0){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
        if(ans[i]!=0x3f3f3f3f)
            cout<<ans[i]<<" ";
        else 
            cout<<0<<" ";
    }
	cout<<"\n";
}	
	return 0;
} 

T3: 思路：按题目所说，建图。小->大建边。跑一遍拓扑排序，有环就不行(入队次数小于节点数)，没环按顺序输出。c

#include<bits/stdc++.h>
using namespace std;
int n;
string s[105];
int G[30][30];
int vis[30];
int in[30];
int ans[30];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n-1;i++){
		string s1=s[i],s2=s[i+1];
		int p=0;
		int min_len=min(s1.size()-1,s2.size()-1);
        bool flag=1;
		while(p<=min_len){
			int c1=s1[p]-'a'+1;
			int c2=s2[p]-'a'+1;
			if(c1!=c2){
				if(G[c1][c2]==0)
				in[c2]++;
				G[c1][c2]=1;
				
                flag=0;
                break;
			}
			p++;
		}
        if(flag){
            if(s1.size()>s2.size()){
                cout<<"Impossible";
                return 0;
            }
        }
	}
	queue<int>q;
	for(int i=1;i<=26;i++){
		for(int j=1;j<=26;j++)vis[j]=0;
		q.push(i);
		while(q.size()){
			int p=q.front();
			q.pop();
            if(vis[p]==0)
			vis[p]=1;
            else {
                cout<<"Impossible";
                return 0;
            }
            for(int i=1;i<=26;i++){
                if(i!=p&&G[p][i]){
                    q.push(i);
                }
            }
		}
	}
	for(int i=1;i<=26;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(q.size()){
		int p=q.front();
		q.pop();
		ans[p]++;
		cout<<(char)(p+'a'-1);
		for(int i=1;i<=26;i++){
			if(i!=p&&G[p][i]){
				in[i]--;
				if(in[i]==0)q.push(i);
			}
		}
	}
	for(int i=1;i<=26;i++){
		if(ans[i]==0){
			cout<<(char)(i+'a'-1);
		}
	}
	return 0;
}

T4: 思路：找有几个环。捕鼠器放在每个环内任意一个节点都能保证