首页 > 代码库 > UVa11324 最大团 The Largest Clique-有向图强连通分量&DP

UVa11324 最大团 The Largest Clique-有向图强连通分量&DP

https://vjudge.net/problem/UVA-11324

给定一张有向图G,求一个节点数目最大的节点集,使得该集合中的任意两个节点u和v满足:要么u可以到达v,要么v可以到达u(u,v相互可达也算满足),要求输出最大的节点数

Given a directed graph G, consider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Create a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the transitive closure of G. We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique.

Input The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50, 000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G.

Output For each test case, output a single integer that is the size of the largest clique in T(G).

Sample Input 1 5 5 1 2 2 3 3 1 4 1 5 2

Sample Output 4

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #include<cstring> 5 using namespace std; 6 const int maxn=1010; 7 struct Edge{ 8     int go,next; 9 };10 struct InputEdge{11     int from,to;12 };13 int T,a,b,n,m,book[maxn],bcc_count,v[maxn],end[maxn],end2[maxn],map[maxn][maxn],bcc_node[maxn],mem[maxn];14 vector<int> G[maxn],G2[maxn];15 vector<InputEdge> inputedge;16 vector<int> S;17 void init(){18     memset(v,0,sizeof(v));19     memset(book,0,sizeof(book));20     bcc_count=0;21     //memset(end,0,sizeof(end));22     //memset(end2,0,sizeof(end2));23     S.clear();24     for(int i=1;i<=n;i++){25         G[i].clear();26         G2[i].clear();27     }28     memset(map,0,sizeof(map));29     inputedge.clear();30     memset(bcc_node,0,sizeof(bcc_node));31     memset(mem,0,sizeof(mem));32 }33 void add(int from,int to){34     //Edge e;e.go=to;e.next=end[from];G.push_back(e);end[from]=G.size()-1;35     G[from].push_back(to);36 }37 void add2(int from,int to){38     //Edge e;e.go=to;e.next=end2[from];G2.push_back(e);end2[from]=G2.size()-1;39     G2[from].push_back(to);40 }41 void dfs(int u){42     v[u]=1;43     for(/*int i=end[u];i;i=G[i].next*/int i=0;i<G[u].size();i++){44         //int go=G[i].go;45         int go=G[u][i];46         if(!v[go]) dfs(go);47     }48     S.push_back(u);49 }50 void dfs2(int u){51     book[u]=bcc_count;52     bcc_node[bcc_count]++;53     for(/*int i=end2[u];i;i=G2[i].next*/int i=0;i<G2[u].size();i++){54         //int go=G2[i].go;55         int go=G2[u][i];56         if(!book[go]) dfs2(go);57     }58 }59 int dp(int x){60     if(mem[x]) return mem[x];61     int& ans=mem[x];62     for(int i=1;i<=bcc_count;i++) if(i!=x&&map[i][x]) ans=max(ans,dp(i)+bcc_node[x]);63     if(!ans) ans=bcc_node[x];64     return ans;65 }66 int main()67 {68     scanf("%d",&T);69     while(T--){70         scanf("%d %d",&n,&m);71         init();72         for(int i=1;i<=m;i++){73             scanf("%d %d",&a,&b);74             add(a,b);add2(b,a);75             inputedge.push_back((InputEdge){a,b});76         }77         for(int i=1;i<=n;i++) if(!v[i]) dfs(i);78         for(int i=n-1;i>=0;i--) if(!book[S[i]]){79             bcc_count++;80             dfs2(S[i]);81         }82         if(bcc_count==1){83             printf("%d\n",n);84             continue;85         }86         for(int i=0;i<inputedge.size();i++){87             InputEdge& e=inputedge[i];88             map[book[e.from]][book[e.to]]=1;89         }90         int ans=0;91         for(int i=1;i<=bcc_count;i++)92             ans=max(ans,dp(i));93         printf("%d\n",ans);94     }95     return 0;96 }

用邻接表存图求BCC会出错....

UVa11324 最大团 The Largest Clique-有向图强连通分量&DP