[Codeforces 919D]Substring

[Codeforces 919D]Substring - 1700

문제 설명 : 

directed edge로 구성된 그래프가 있다. 그래프의 각 노드에는 알파벳이 배정되어있다. 그래프의 경로를 지나면서 거쳐가는 노드들의 알파벳중에서 최대 빈도수를 구하는 문제이다.  무수히 많은 빈도수가 나올 때는 -1을 출력한다.

풀이 : 

일단 그래프에서 사이클이 존재하는 경우 사이클 내에 있는 알파벳은 무수히 많이 등장할 수 있으므로 -1을 출력하면 된다. 만약 사이클이 없는게 확인된 그래프라면 위상정렬 알고리즘을 사용한다. 각 노드는 각 알파벳이 최대 몇 번 등장할 수 있는지 저장할 수 있는 freq[][]배열을 만든다. 그래서 다음 노드(next)에서 freq배열은 현재 노드의 freq배열과 같은 값을 가지면서, 다음 노드에 배정된 알파벳의 인덱스는 1 증가시켜주면 된다. 만약 next노드에 연결된 다른 노드들이 여러개라면 freq 배열의 값 중에서 가장 큰 값만 취하면 된다.

그래프에서 사이클을 판별하는 별도의 알고리즘이 있기는 하나, 나는 그냥 scc로 판별하기로 했다. 그 알고리즘은 레퍼런스로 따로 남기겠다.  실제로는 scc로 사이클을 판별할 필요도 없이 위상정렬 안의 while()문 안에서 pop()이 일어나는 횟수가 전체 노드 수(V)와 같은지 확인해주어도 사이클을 가지는지 판별해 줄 수 있다.

주의할 점 : 

-

배운 점 : 

사이클을 체크하고, 위상정렬까지 이용해야한다는 생각까지는 근접했는데 아깝게 풀지 못한 문제였다. 사이클을 체크하는데 scc보다는 간단한 알고리즘이 존재한다는 점, 그리고 그래프에서 시작점부터 끝점까지 봐야하는 경우(이 문제의 경우 최대한 긴 경로들의 집합을 만들어야 함) 위상정렬 알고리즘을 이용해야 한다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 300009;
 
vector<int> graph[SIZE];
char str[SIZE];
int inD[SIZE],idx[SIZE],finished[SIZE];
int ans=1,cnt=1;
int freq[SIZE][33]={0};
vector<int> st;
 
int scc_dfs(int node){
    idx[node]=cnt++;
    int ret=idx[node];
    st.push_back(node);
 
    for(int next:graph[node]){
        if(idx[next]==0){
            ret=min(ret,scc_dfs(next));
        }
        else if(!finished[next]){
            ret=min(ret,idx[next]);
        }
    }
 
    if(ret==idx[node]){
        vector<int>tmp;
        while(1){
            int top=st.back();  st.pop_back();
            tmp.push_back(top);
            finished[top]=1;
            if(top==node) break;
        }
        if(tmp.size()>1) ans=-1;
    }
    return ret;
}
 
int main(){
    int V,E;    scanf("%d %d",&V,&E);
    scanf("%s",str+1);
 
    for(int i=0 ; i<E ; i++){
        int u,v;    scanf("%d %d",&u,&v);
        if(u==v){printf("-1\n"); return 0;}
        graph[u].push_back(v);
        inD[v]++;
    }
 
    for(int i=1 ; i<=V ; i++)
        if(idx[i]==0) scc_dfs(i);
 
    if(ans==-1){printf("-1\n"); return 0;}
 
    queue<int> q;
    for(int i=1 ; i<=V ; i++)
        if(inD[i]==0) q.push(i);
 
    int ans=0;
    while(!q.empty()){
        int cur=q.front();  q.pop();
        int &ret=freq[cur][str[cur]-'a'];
        ret++;
        ans=max(ans,ret);
 
        for(int next:graph[cur]){
            for(int i=0 ; i<26 ; i++){
                freq[next][i]=max(freq[next][i],freq[cur][i]);
            }
 
            if(--inD[next]==0){
                q.push(next);
            }
        }
    }
 
    printf("%d\n",ans);
    return 0;
}