首页 > 代码库 > 图论trainning-part-2 C. The Largest Clique
图论trainning-part-2 C. The Largest Clique
C. The Largest Clique
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.
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 nand 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 ofG 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.
For each test case, output a single integer that is the size of the largest clique in T(G).
Sample input
15 51 22 33 14 15 2
Output for sample input
4
解题：强连通子图的求解，缩点，DAG上的动态规划。先求出所有的强连通子图后，再对各个强连通子图进行缩点，所谓缩点，即为把这个强连通块作为一个点，进行新图的建立。原来图上的任意一点必然属于某个强连通块。所以根据各点所在的连通块，进行新图的建立，注意方向性，DAG上的动态规划是对于有向图而言的，所以必须保证方向的正确性。建立新图后，求DAG上的最长路径即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define INF 0x3f3f3f3f15 using namespace std;16 const int maxn = 1010;17 int low[maxn],dfn[maxn],iindex,sccBlocks;18 bool instack[maxn],vis[maxn];19 int belong[maxn],val[maxn],dp[maxn],n,m;20 stack<int>s;21 vector<int>g[maxn];22 vector<int>mp[maxn];23 void tarjan(int u){24 dfn[u] = low[u] = ++iindex;25 instack[u] = true;26 s.push(u);27 for(int i = 0; i < g[u].size(); i++){28 int v = g[u][i];29 if(!dfn[v]){30 tarjan(v);31 low[u] = min(low[u],low[v]);32 }else if(instack[v] && low[u] > dfn[v]) low[u] = dfn[v];33 }34 if(dfn[u] == low[u]){35 int v;36 sccBlocks++;37 do{38 v = s.top();39 s.pop();40 instack[v] = false;41 belong[v] = sccBlocks;42 }while(u != v);43 }44 }45 int dag(int u){46 if(dp[u]) return dp[u];47 else if(mp[u].size() == 0) return dp[u] = val[u];48 int ans = 0;49 for(int v = 0; v < mp[u].size(); v++){50 ans = max(ans,dag(mp[u][v]));51 }52 return dp[u] = ans+val[u];53 }54 int main(){55 int t,u,v,i,j;56 scanf("%d",&t);57 while(t--){58 scanf("%d%d",&n,&m);59 for(i = 0; i <= n; i++){60 g[i].clear();61 dfn[i] = low[i] = 0;62 instack[i] = false;63 val[i] = belong[i] = 0;64 dp[i] = 0;65 mp[i].clear();66 }67 for(i = 0; i < m; i++){68 scanf("%d%d",&u,&v);69 g[u].push_back(v);70 }71 iindex = sccBlocks = 0;72 for(i = 1; i <= n; i++)73 if(!dfn[i]) tarjan(i);74 for(u = 1; u <= n; u++){75 val[belong[u]]++;76 memset(vis,false,sizeof(vis));77 for(j = 0; j < g[u].size(); j++){78 v = g[u][j];79 if(!vis[belong[v]] && belong[v] != belong[u]){80 vis[belong[v]] = true;81 mp[belong[u]].push_back(belong[v]);82 }83 }84 }85 int ans = 0;86 for(i = 1; i <= sccBlocks; i++)87 ans = max(ans,dag(i));88 printf("%d\n",ans);89 }90 return 0;91 }