題目描述

In this problem, we would like to talk about unreachable sets of a directed acyclic graph G = (V, E). In?mathematics a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is a graph such that?there is no way to start at any node and follow a consistently-directed sequence of edges in E that eventually loops?back to the beginning again.
A node set denoted by V UR ? V containing several nodes is known as an unreachable node set of G if, for each?two different nodes u and v in V UR , there is no way to start at u and follow a consistently-directed sequence of?edges in E that ?nally archives the node v. You are asked in this problem to calculate the size of the maximum?unreachable node set of a given graph G.

輸入

The input contains several test cases and the first line contains an integer T (1 ≤ T ≤ 500) which is the number of?test cases.
For each case, the first line contains two integers n (1 ≤ n ≤ 100) and m (0 ≤ m ≤ n(n ? 1)/2) indicating the?number of nodes and the number of edges in the graph G. Each of the following m lines describes a directed edge?with two integers u and v (1 ≤ u, v ≤ n and u 6= v) indicating an edge from the u-th node to the v-th node. All?edges provided in this case are distinct.
We guarantee that all directed graphs given in input are DAGs and the sum of m in input is smaller than 500000.

輸出

For each test case, output an integer in a line which is the size of the maximum unreachable node set of G.

樣例輸入

3 4 4 1 2 1 3 2 4 3 4 4 3 1 2 2 3 3 4 6 5 1 2 4 2 6 2 2 3 2 5

樣例輸出

2 1 3

題解：先求出來傳遞閉包，并拆點，用二分圖求原圖的最小路徑覆蓋。
#include <bits/stdc++.h> using namespace std; const int N=100; bool graph[N][N],visited[N]; int n,match[N]; bool djk(int u) {if(visited[u]) return false;visited[u]=true;for(int v=0;v<n;v++){if(graph[u][v]&&(match[v]==-1||djk(match[v]))){match[v]=u;return true;}}return false; } int main(){ios::sync_with_stdio(false);int T;cin>>T;while(T--){int m;cin>>n>>m;memset(graph,0,sizeof(graph));for(int i=0;i<m;i++){int a,b;cin>>a>>b;graph[a-1][b-1]=true;}for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){graph[i][j] |=graph[i][k]&&graph[k][j];}}}int result=n;memset(match,-1,sizeof(match));memset(visited,0,sizeof(visited));for(int i=0;i<n;i++){if(djk(i)){result--;memset(visited,0,sizeof(visited));}}cout<<result<<endl;} } View Code

二分圖：

二分圖的性質

二分圖中，點覆蓋數是匹配數。
????(1) 二分圖的最大匹配數等于最小覆蓋數，即求最少的點使得每條邊都至少和其中的一個點相關聯，很顯然直接取最大匹配的一段節點即可。
????(2) 二分圖的獨立數等于頂點數減去最大匹配數，很顯然的把最大匹配兩端的點都從頂點集中去掉這個時候剩余的點是獨立集，這是|V|-2*|M|，同時必然可以從每條匹配邊的兩端取一個點加入獨立集并且保持其獨立集性質。
????(3) DAG的最小路徑覆蓋，將每個點拆點后作最大匹配，結果為n-m，求具體路徑的時候順著匹配邊走就可以，匹配邊i→j',j→k',k→l'....構成一條有向路徑。

? ? ?（4）最大匹配數=左邊匹配點+右邊未匹配點。因為在最大匹配集中的任意一條邊，如果他的左邊沒標記，右邊被標記了，那么我們就可找到一條新的增廣路，所以每一條邊都至少被一個點覆蓋。

? ? ?（5）最小邊覆蓋=圖中點的個數-最大匹配數=最大獨立集。

?

二分圖的判定

?

二分圖是這樣一個圖： 有兩頂點集且圖中每條邊的的兩個頂點分別位于兩個頂點集中，每個頂點集中沒有邊直接相連接！

　無向圖G為二分圖的充分必要條件是，G至少有兩個頂點,且其所有回路的長度均為偶數。

　判斷二分圖的常見方法是染色法： 開始對任意一未染色的頂點染色，之后判斷其相鄰的頂點中，若未染色則將其染上和相鄰頂點不同的顏色， 若已經染色且顏色和相鄰頂點的顏色相同則說明不是二分圖，若顏色不同則繼續判斷，bfs和dfs可以搞定！

易知：任何無回路的的圖均是二分圖。

參考：http://dsqiu.iteye.com/blog/1689505

模板：

有向無環圖（DAG）的最小路徑覆蓋

轉載于:https://www.cnblogs.com/smallocean/p/8743013.html

總結

以上是生活随笔為你收集整理的The Maximum Unreachable Node Set的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。