练习

//图的存储与遍历 
#include<bits/stdc++.h>
using namespace std;
vector<int> g[11];
queue<int> f;
int vis[101],visw[101];
int a[11][11];
void dfs(int x){
    vis[x]=true;
    cout<<x<<" ";
    for(int i=0; i<g[x].size(); i++){
        int c=g[x][i];
        if(!vis[c]) dfs(c);
    }
}
void bfs(int y){
    f.push(y);
    visw[y]=true;
    while(!f.empty()){
        y=f.front();
        cout<<y<<" ";
        f.pop();
        for(int i=0; i<g[y].size(); i++){
            int l=g[y][i];
            if(!visw[l]){
                f.push(l);
                visw[l]=true;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int k=1; k<=n; k++){
            cin>>a[i][k];
            if(a[i][k]==1) g[i].push_back(k);
        }
    }
    for(int i=1; i<=n; i++){
        cout<<i<<" ";
        for(int k=0; k<g[i].size();k++){
            cout<<g[i][k]<<" ";
        }
        cout<<endl;
    }
    for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
    cout<<endl;
    for(int i=1; i<=n; i++) if(!visw[i]) bfs(i);
    return 0;
}

//sixdeg
#include<bits/stdc++.h>
using namespace std;
vector<int> g[1001];
queue<int> f;
int visw[1001],maxn,sy[1001]={0},maxs=0;
int a[11][11];
void bfs(int y){
    f.push(y);
    visw[y]=true;
    while(!f.empty()){
        y=f.front();
        f.pop();
        for(int i=0; i<g[y].size(); i++){
            int l=g[y][i];
            if(!visw[l]){
                sy[l]=sy[y]+1;
                maxs=max(maxs,sy[l]);
                f.push(l);
                visw[l]=true;
            }
        }
    }
}
int main(){
    int c,p;
    cin>>c>>p;
    for(int i=1; i<=p; i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(1);
    cout<<maxs;
    return 0;
}

//拓扑排序 
#include<bits/stdc++.h>
using namespace std;
int n,m,d[1005]; 
priority_queue<int,vector<int>,greater<int> > q;
vector<int> g[1005],ans;
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        d[y]++;
    }
    for(int i=1; i<=n; i++){
        if(d[i]==0) q.push(i);
    }
    while(!q.empty()){
        int f=q.top();
        q.pop();
        ans.push_back(f);
        for(int i=0; i<g[f].size(); i++){
            int t=g[f][i];
            d[t]--;
            if(d[t]==0) q.push(t);
        }
    }
    if(ans.size()!=n) {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0; i<ans.size(); i++) cout<<ans[i]<<" ";
    return 0;
}

//骑马修栅栏 
#include<bits/stdc++.h>
using namespace std;
int mp[505][505];
int du[505];
int path[1030],k;
int f,minn=INT_MAX,maxn=0,a,b;
void dfs(int x){
    for(int i=minn; i<=maxn; i++){
        if(mp[x][i]){
            mp[x][i]--;mp[i][x]--;
            dfs(i);
        }
    }
    path[k++]=x;
}
int main(){
    cin>>f;
    for(int i=1; i<=f; i++){
        cin>>a>>b;
        mp[a][b]++;mp[b][a]++;
        du[a]++;du[b]++;
        minn=min(minn,min(a,b));
        maxn=max(maxn,max(a,b));
    }
    int start=minn;
    for(int i=minn; i<=maxn; i++){
        if(du[i]%2){
            start=i;
            break;
        }
    }
    dfs(start);
    for(int i=k-1; i>=0; i--) cout<<path[i]<<endl;
    return 0;
}

//传话 
#include<bits/stdc++.h>
using namespace std;
int l[1001][10001];
int n,m,a,b,t;
bool v[1001],huan[1001];
void dfs(int x){
    if(huan[t]) return ;
    v[x]=1;
    if(x==t){
        huan[t]=1;
        return ;
    }
    for(int i=1;i<=l[x][0];i++)
        if(!v[l[x][i]]) dfs(l[x][i]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        l[a][0]++;
        l[a][l[a][0]]=b;
    }   
    for(t=1;t<=n;t++){
        memset(v,0,sizeof(v));
        for(int i=1;i<=l[t][0];i++)
            dfs(l[t][i]);
    }    
    for(int i=1;i<=n;i++)
        if(huan[i]) cout<<"T"<<endl;
        else cout<<"F"<<endl;
    return 0;
}

//奖金 
#include<bits/stdc++.h>
using namespace std;
int a[10001][301]={0},into[10001],ans[10001],m,n,money;
void init(){
    int i,x,y;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>x>>y;
        a[y][0]++;
        a[y][a[y][0]]=x;
        into[x]++;
    }
}
bool tops(){
    int t,tot=0,k=0,i,j;
    while(tot<n){
    t=0;
    for(i=1; i<=n; i++)
        if(into[i]==0){
            tot++;t++;money+=100;
            ans[t]=i;
            into[i]=0xfffffff;
        }
        if(t==0) return false;
        money+=k*t;k++;
        for(i=1; i<=t; i++)
            for(j=1; j<=a[ans[i]][0]; j++) into[a[ans[i]][j]]--;
        }
        return true;
    }
int main(){
    init(); money=0;
    if(tops()) cout<<money<<endl;
    else cout<<"Poor Xed"<<endl;
    return 0;
}