글 읽기 - 강한 연결(scc) 관련 문제 풀기 컨셉을 어떻게 잡아야 할까요?

keh0711 8년 전 0

처음 문제를 풀때 잡은 컨셉이 한 정점을 선택하면 이와 연결되어 같이 가야하는 정점의 수를 계산했습니다. 이렇게 문제방향을 잡으니 샘플케이스 2,3번째 케이스는 해결되지만 1번은 풀리지 않습니다.

생각해보니 버스에 탈 수 있는 자리가 넉넉할 경우, 여러 부분집합(컴포넌트)의 원소수를 조합해야 하는데...참 막막하네요

혹시나 참고가 될까하여 소스를 같이 올립니다.

#include "stdio.h"
#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
int n, cp, finish[1001], discover[1001], cnt=1, sccCnt=1, _max;
int map[1001][1001];
stack<int> scc;
queue<int> que;
int sccId[1001];

int f(int here)
{
    discover[here]=cnt++;
    int ret=discover[here];
    for(int there=1;there<=n;there++)
    {
        //there이 아직 가지 않은 곳일 경우에는 깊이탐색 후, there과 연결된 정점수를 누적
        if(map[here][there]==1&&discover[there]==0)
        {
            //cout<<here<<" "<<there<<endl;
            scc.push(there);
            int tmp=f(there);
            if(tmp>discover[here])
                sccId[here]+=sccId[tmp];
            ret=min(discover[here], tmp);
        }
        //역행간선일 경우에는 사이클이 존재한다. 사이클 계산하기 준비,
        else if(map[here][there]==1&&discover[there]<discover[here]
                                                        &&finish[there]!=1)
        {
            ret=min(ret, discover[there]);
            //cout<<"ret "<<ret<<endl;
        }
        //이미 깊이탐색으로 끝난 정점에 진입을 시도한다. 들어갈 필요없이 there에 연결된 정점수 받기
        else if(map[here][there]==1&&discover[there]<discover[here]
                                                        &&finish[there]==1)
        {
            sccId[here]+=sccId[there];
        }
    }
    //해당 정점과 연결된 수를 계산한다.
    int cycle=0;
    if(discover[here]==ret)
    {
        while (scc.size())
        {
            int st=scc.top();
            scc.pop();
            que.push(st);
            cycle++;
            if(st==here)
                break;
        }
        sccCnt++;
        while (true)
        {
            int st=que.front();
            que.pop();
            sccId[st]+=cycle;
            if(st==here)
                break;
        }
    }
    finish[here]=1;
    return ret;
}

int main(int argc, const char * argv[]) {
    freopen("input.txt","r", stdin);
    scanf("%d %d", &n, &cp);
    int b;
    for(int a=1;a<=n;a++)
    {
        scanf("%d", &b);
        map[a][b]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(discover[i]==0)
        {
            scc.push(i);
            f(i);
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        cout<<i<<":"<<sccId[i]<<endl;
    }
    cout<<_max<<endl;
    
    return 0;
}