HDU 2767 강 연결 분량
제목: 변 을 얼마나 넣 으 면 강 한 연결 분량 이 1 인 그림 이 되 느 냐 고 물 었 다.
사고: 간단 한 강 한 연결, 축소 한 후에 입도 와 출 도 를 찾 으 면 됩 니 다.
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=20010;
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> vs;
bool used[maxn];
int cmp[maxn],V;
void add_edge(int from,int to){
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v){
used[v]=1;
for(int i=0;i<G[v].size();i++){
if(!used[G[v][i]]) dfs(G[v][i]);
}
vs.push_back(v);
}
void rdfs(int v,int k){
used[v]=1;
cmp[v]=k;
for(int i=0;i<rG[v].size();i++){
if(!used[rG[v][i]]) rdfs(rG[v][i],k);
}
}
int scc(){
memset(used,0,sizeof(used));
vs.clear();
for(int v=0;v<V;v++) if(!used[v]) dfs(v);
memset(used,0,sizeof(used));
int k=0;
for(int i=vs.size()-1;i>=0;i--){
if(!used[vs[i]]) rdfs(vs[i],k++);
}
return k;
}
int A[maxn*3],B[maxn*3];
int in[maxn],out[maxn];
int main(){
int T,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&V,&m);
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=0;i<maxn;i++){
G[i].clear();
rG[i].clear();
}
vs.clear();
for(int i=0;i<m;i++){
scanf("%d%d",&A[i],&B[i]);
A[i]--;B[i]--;
add_edge(A[i],B[i]);
}
int ans=scc();
if(ans==1){
printf("0
");
continue;
}
for(int i=0;i<m;i++){
int a=cmp[A[i]],b=cmp[B[i]];
if(a!=b){
in[b]++;out[a]++;
}
}
int sum1=0,sum2=0;
for(int i=0;i<ans;i++){
if(in[i]==0) sum1++;
if(out[i]==0) sum2++;
}
printf("%d
",max(sum1,sum2));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.