poj3713(무방향도 3연통 여부 판단)
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 1160
Accepted: 270
Description
After recapturing Sylla, the Company plans to establish a new secure system, a transferring net! The new system is designed as follows:
The Company staff choose N cities around the nation which are connected by "security tunnels"directly or indirectly. Once a week, Sylla is to be transferred to another city through the tunnels. As General ordered, the transferring net must reach a certain security level that there are at least 3 independent paths between any pair of cities a, b. When General says the paths are independent, he means that the paths share only a and b in common.
Given a design of a transferring net, your work is to inspect whether it reaches such security level.
Input
The input consists of several test cases. For each test case, the first line contains two integers, N ≤ 500 and M ≤ 20000. indicating the number of cities and tunnels. The following M lines each contains two integers a and b (0 ≤ a, b < N), indicating the city a and city b are connected directly by a tunnel.
The input ends by two zeroes.
Output
For each test case output "YES"if it reaches such security level, "NO"otherwise.
Sample Input
4 6
0 1
0 2
0 3
1 2
1 3
2 3
4 5
0 1
0 2
0 3
1 2
1 3
7 6
0 1
0 2
0 3
1 2
1 3
2 3
0 0
Sample Output
YES
NO
NO
Source
POJ Founder Monthly Contest – 2008.12.28, Dagger
제목:http://poj.org/problem?id=3713
분석: 삼연통은 생각이 없군요. 다른 사람의 문제풀이를 보면 하나하나 한 점을 제거한 다음에 절단점이 존재하거나 연결되었는지 판단합니다. 만약에 절단점이 존재하거나 연결되지 않으면 삼연통이 아닙니다...이상하네, 시간이 너무 징그러워.그 몇 백 ms 짜리가 어떻게 왔는지 모르겠다
코드:
#include<cstdio>
using namespace std;
const int mm=44444;
const int mn=555;
int t[mm],p[mm];
int h[mn],dfn[mn],low[mn],du[mn];
int i,j,k,n,m,idx;
bool dfs(int u,int fa)
{
dfn[u]=low[u]=++idx;
for(int i=h[u],v,son=0;i>=0;i=p[i])
if(!dfn[v=t[i]])
{
++son;
if(dfs(v,u))return 1;
if(fa==-1&&son>1||fa!=-1&&dfn[u]<=low[v])return 1;
if(low[u]>low[v])low[u]=low[v];
}
else if(v!=fa&&low[u]>dfn[v])low[u]=dfn[v];
return 0;
}
bool tarjan()
{
int i,j,k;
for(i=0;i<n;++i)
if(du[i]<3)return 0;
for(i=0;i<n;++i)
{
for(j=idx=0;j<n;++j)dfn[j]=0;
dfn[i]=n+n;
for(j=k=0;j<n;++j)
if(!dfn[j])
{
if(++k>1)return 0;
if(dfs(j,-1))return 0;
}
}
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
for(i=k=0;i<n;++i)h[i]=-1,du[i]=0;
while(m--)
{
scanf("%d%d",&i,&j);
t[k]=j,p[k]=h[i],h[i]=k++;
t[k]=i,p[k]=h[j],h[j]=k++;
++du[i],++du[j];
}
puts(tarjan()?"YES":"NO");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
클립보드로 컨텐트 복사//txt参数为显示和复制的文本内容 function copyToBoard(txt) { if(window.clipboardData) { window.clipboardData.clearData(); window.clipb...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.