HDU 3639 강 연통 축 점 최적화

제목: 한 무리의 아이들 이 독수리 로 병 아 리 를 잡 고 놀 고 있 습 니 다. 독수리 가 되 고 싶 은 사람 이 적지 않 기 때문에 아이들 은 투 표를 통 해 생 겨 났 습 니 다. 그러나 투 표 는 전달 성 이 있 습 니 다. A 는 B, B 는 C 를 지지 합 니 다. 그러면 C 는 2 표 (A. B 총 2 표) 를 얻 은 다음 에 가장 많은 표를 얻 은 사람 이 누구 인지, 가장 많은 표를 얻 을 수 있 는 표 가 몇 장 이 냐 고 물 었 습 니 다.
사고방식: 원시 적 인 사고방식 은 모든 점 에 대해 DFS 를 한 번 뛰 고 통 계 를 하 는 것 이다. 그러나 case 가 비교적 많 기 때문에 반드시 시간 을 초과 해 야 한다. 그래서 우 리 는 최적화 해 야 한다. 이 문 제 는 X 개의 점 이 자신 을 뿌리 로 하고 I, 수출 이 가장 큰 X 와 해당 하 는 I 를 포함 하 는 것 으로 바 뀔 수 있다. 그러나 이렇게 하고 싶 지 않다. 우 리 는 보통 뿌리 에서 노드 까지 이다. 이 문 제 는 노드 에서 뿌리 까지, 생각 하지 않 는 다.우 리 는 특정한 노드 를 뿌리 로 하고 가장 많이 가 진 아들 노드 의 개수 로 바 꿀 수 있다.그러나 이렇게 하면 시간 을 초과 할 수 있 습 니 다. 그러나 우 리 는 강 한 연결 로 최적화 시 키 고 강 한 연결 점 을 가 진 후에 DFS 를 뛰 는 것 을 고려 할 수 있 습 니 다. 그러나 각 조 의 데이터 가 체인 모양 이 라면 시간 을 초과 할 수 있 습 니 다. 우 리 는 주의해 야 합 니 다. 만약 에 이 노드 가 입 도 를 가지 면 반드시 최 적 화 된 것 이 아 닙 니 다. (이것 은 잘 이해 하고 스스로 생각해 보 세 요)
요약: 그림 이 있 는 문제 에 대해 최적화 가 필요 할 때 강 한 연결 점 으로 생각 할 수 있다. 예 를 들 어 이 문제 가 줄 어 들 지 않 으 면 각 점 에서 적어도 한 번 뛰 고 줄 인 후의 효율 이 큰 폭 으로 향상 된다.
code：

#include
#include
#include
#include
using namespace std;
const int maxn = 7000;
struct edge
{
    int u,v,next;
}e[maxn * 10];
int n,m,tot,cntnode,num,top,cnt;
int head[maxn],dfn[maxn],low[maxn],id[maxn],st[maxn],re[maxn];
int inc[maxn];
bool ins[maxn],vis[maxn],in[maxn];
void init();
void solve(int cas);
void tarjan(int u);
void add_edge(int u,int v);
void dfs(int f,int u);
int main()
{
    int T,cas = 1;
    scanf("%d",&T);
    while(T --){
        scanf("%d%d",&n,&m);
        init();
        for(int i = 0;i < m;i ++){
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(v,u);
        }
        solve(cas ++);
    }
    return 0;
}
void init()
{
    for(int i = 0;i < n;i ++){
        ins[i] = in[i] = false;
        head[i] = dfn[i] = low[i] = -1;
        inc[i] = 0;
    }
    tot = top = cntnode = num = 0;
}
void add_edge(int u,int v)
{
    e[tot].u = u , e[tot].v = v;
    e[tot].next = head[u],head[u] = tot ++;
}
void tarjan(int u)
{
    low[u] = dfn[u] = num ++;
    ins[u] = true;
    st[++ top] = u;
    for(int i = head[u];i != -1;i = e[i].next){
        int v = e[i].v;
        if(dfn[v] == -1){
            tarjan(v);
            if(low[v] < low[u])
                low[u] = low[v];
        }
        else if(ins[v] && dfn[v] < low[u])
            low[u] = dfn[v];
    }
    if(low[u] == dfn[u]){
        int v = -1;
        while(u != v){
            v = st[top --];
            id[v] = cntnode;
            ins[v] = false;
        }
        cntnode ++;
    }
}
void solve(int cas)
{
    for(int i = 0;i < n;i ++)
        if(dfn[i] == -1)  tarjan(i);
    // for(int i = 0;i < n;i ++)
        // printf("I:%d   id:%d
",i,id[i]);
    for(int i = 0;i < n;i ++){
        int idx = id[i];
        inc[idx] ++;
    }
    memset(head,-1,sizeof(head));
    for(int i = 0;i < m;i ++){
        int u = id[e[i].u];
        int v = id[e[i].v];
        if(u != v)in[v] = true;
        add_edge(u,v);
    }
    int ans = -1;
    for(int i = 0;i < cntnode;i ++){
        if(in[i]) continue;
        cnt = 0;
        for(int j = 0;j < cntnode;j ++) vis[j] = false;
        dfs(i,i);
        re[i] = cnt;
        ans = max(ans,cnt);
    }
    vector rec;
    for(int i = 0;i < n;i ++){
        int idx = id[i];
        if(in[idx]) continue;
         if(re[idx] == ans)
             rec.push_back(i);
    }
    printf("Case %d: %d
", cas ++,ans - 1);
    for(int i = 0;i < rec.size();i ++)
        printf("%d%c",rec[i],i == rec.size() - 1 ? '
' : ' ');
}
void dfs(int f,int u)
{
    cnt += inc[u];
    if(vis[u]) return ; 
    vis[u] = true;
    for(int i = head[u];i != -1;i = e[i].next){
        int v = e[i].v;
        if(v == f || v == u || vis[v]) continue;
        dfs(u,v);
    }
}