拓撲排序

圖論中的拓撲排序：
在一個有向圖中，對所有的節點進行排序，要求沒有一個節點指向它前面的節點，

先統計所有節點的入度，對于入度為0的節點就可以分離出來，然后把這個節點指向的節點的入度減一，

一直做改操作，直到所有的節點都被分離出來，

如果最后不存在入度為0的節點，那就說明有環，不存在拓撲排序，也就是很多題目的無解的情況，

簡單的說就是：一步步的在原圖上去掉入度為0的點，同時把這個點連得邊（也就是出度的邊）也去掉，

理解起來就是是這樣的
演示一下的話就是（回頭再加吧）沒找的畫圖工具
那一個題目說一下吧：
有點繞，應該算中的的題型：
B. Ponds

題目大意就是：
找到回路然后計算出回路中的點個數，奇數則加上各個點權值，偶數則不用管，不構成回路的不參加計算，
題目分析：
難點就是利用拓撲排序來去掉分支找出回路，然后用BFS找出哪個對應的回路，對了還有建圖的程序，
再細節的說一下吧 ，：首先我們把給出的這些邊轉化成兩個單向邊，這是建圖程序（不細說了），之后就要去度刪邊了，先找到度為零的孤點直接刪去就行，之后就是度為1的具有單邊性質（構不成回路）刪去時要注意，刪這個點之后可能會影響和他相連的另一個點度的變化，所以還要考慮跟他相連的哪個點的度-1；再去判斷回圈判斷，這中用到佇列優化，因為我們要存放度為1的點，這樣我們就不會漏或者丟點了，這樣我們回路也就找出來了，然后我們就要判斷每個獨立回路中有多少點了，這決定了他要不要成為代價（奇數算偶數扔），也就是DFS程序，這中間把點的個數，和點權和都要記錄下來，為了之后用到，

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxm=1e5+1010;
const int maxn=1e4+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
	int x=0;
	bool t=false;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}

/*
vector<ll> m1;
vector<ll> m2;
priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆 		小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下   	大根堆  	大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,num,ans,res,cnt,flag,maxx,minn;
bool visited[maxn];
ll deg[maxn];
ll head[maxn],vis[maxn];

struct node {
	ll to;
	ll next;
}vv[maxm];
queue<ll> q;
void add(ll u,ll v){
	vv[cnt].to=v;
	vv[cnt].next=head[u];
	head[u]=cnt++;
}

void inte(){
	while(!q.empty())///清空佇列
    {
        q.pop();
    }
    cnt=0;
    ans=0;
    memset(head,-1,sizeof(head));
    memset(deg,0,sizeof(deg));///度為多少
    memset(visited,false,sizeof(visited));///是否走過

	sf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) sf("%lld",&vis[i]);

	for(int i=1;i<=m;i++){
			ll u,v;
		sf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
		deg[u]++;
		deg[v]++;
	}
	return ;
}
void topsort(){
	for(int i=1;i<=n;i++){
		if(deg[i]==0){///孤立點
			visited[i]=true;
		}else if(deg[i]==1){///找到出度為一的點；
			visited[i]=true;
			q.push(i);
		}
	}
	while(!q.empty()){
		ll tmp=q.front();
		q.pop();
		for(int i=head[tmp];i!=-1;i=vv[i].next){
			ll r=vv[i].to;///對應的
			deg[r]--;
			if(deg[r]==0){
				visited[r]=true;
			}else if(deg[r]==1){
				visited[r]=true;
				q.push(r);
			}
		}
	}

}
void dfs(ll u,ll gen){
	visited[u]=true;
	num++;
	res+=vis[u];
	for(int i=head[u];i!=-1;i=vv[i].next){
		ll r=vv[i].to;
		if(!visited[r]&&r!=gen){
			dfs(r,u);
		}
	}
	return ;
}
#define read read()
int main(){
	cin>>t;
	while(t--){
		inte();
		topsort();
		sum=0;
		for(int i=1;i<=n;i++){
			if(!visited[i]){
				num=0;
				res=0;
				dfs(i,0);
				if(num%2==1){
					sum+=res;
				}
			}

		}
		pf("%lld\n",sum);
	}

	return 0;
}

前面頭檔案挺長的，沒啥用，可以刪掉哦，

找了一個小模板可以看下：

    queue<int>q;
    vector<int>edge[n];
    for(int i=0;i<n;i++)  //n  節點的總數
        if(in[i]==0) q.push(i);  //將入度為0的點入佇列
    vector<int>ans;   //ans 為拓撲序列
    while(!q.empty())
    {
        int p=q.front(); q.pop(); // 選一個入度為0的點，出佇列
        ans.push_back(p);
        for(int i=0;i<edge[p].size();i++)
        {
            int y=edge[p][i];
            in[y]--;
            if(in[y]==0)
                q.push(y);  
        }
    }
    if(ans.size()==n)   
    {
        for(int i=0;i<ans.size();i++)
            printf( "%d ",ans[i] );
        printf("\n");
    }
    else printf("No Answer!\n");   //  ans 中的長度與n不相等，就說明無拓撲序列