HDU 2767 강 연결 분량

2140 단어 데이터 구조ACM
클릭 하여 링크 열기
제목: 변 을 얼마나 넣 으 면 강 한 연결 분량 이 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; }

좋은 웹페이지 즐겨찾기