uva 11324 The Largest Clique(그림-tarjan, 동적 계획)
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 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.
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
Output for sample input
4
Zachary Friggstad
제목 대의:
T조 테스트 데이터는 지향도 G를 주고 결점수가 가장 큰 결점 집합을 구하여 이 결점 중 임의의 두 개의 결점 u와 v가 만족하도록 한다. u는 v에 도달할 수 있거나 v는 u에 도달할 수 있다(u와 v는 서로 도달할 수 있다).
문제 해결 방법:
'같은 강연통 분량 중의 점을 모두 선택하거나 선택하지 않는다.강연통분량의 수축점을 얻어SCC도를 얻어 모든SCC결점의 권리가 그의 결점수와 같게 하면 제목은SCC도에서 가장 큰 권한을 구하는 경로로 바뀐다.SCC 그림은 DAG이기 때문에 동적 기획으로 해답을 구할 수 있다.“
문제 해결 코드:
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1100;
const int maxm=51000;
struct edge{
int u,v,next;
edge(int u0=0,int v0=0){
u=u0;v=v0;
}
}e[maxm];
int n,m,head[maxn],dfn[maxn],low[maxn],mark[maxn],w[maxn],color[maxn],dp[maxn],cnt,nc,index;
vector vec;
vector > dfsmap;
void addedge(int u,int v){
e[cnt]=edge(u,v);e[cnt].next=head[u];head[u]=cnt++;
}
void input(){
cnt=nc=index=0;
scanf("%d%d",&n,&m);
vec.clear();
for(int i=0;i<=n;i++){
w[i]=dfn[i]=0;
mark[i]=false;
color[i]=dp[i]=head[i]=-1;
}
int u,v;
while(m-- >0){
scanf("%d%d",&u,&v);
addedge(u,v);
}
}
void tarjan(int s){
dfn[s]=low[s]=++index;
mark[s]=true;
vec.push_back(s);
for(int i=head[s];i!=-1;i=e[i].next){
int d=e[i].v;
if(!dfn[d]){
tarjan(d);
low[s]=min(low[d],low[s]);
}else if(mark[d]){
low[s]=min(low[s],dfn[d]);
}
}
if(dfn[s]==low[s]){
nc++;
int d;
do{
d=vec.back();
vec.pop_back();
color[d]=nc;
mark[d]=false;
w[nc]++;
}while(d!=s);
}
}
int DP(int s){
if(dp[s]!=-1) return dp[s];
int ans=w[s];
for(int i=0;ians) ans=DP(d)+w[s];
}
return dp[s]=ans;
}
void solve(){
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
dfsmap.clear();
dfsmap.resize(nc+1);
for(int i=0;i"<ans) ans=DP(i);
//cout<0){
input();
solve();
}
return 0;
}
전재 대상:https://www.cnblogs.com/toyking/p/3893147.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.