【NOI2008】假面舞會（圖論，搜尋）

題面

Description

一年一度的假面舞會又開始了，棟棟也興緻勃勃的參加了今年的舞會。今年的面具都是主辦方特别定制的。每個參加舞會的人都可以在入場時選擇一個自己喜歡的面 具。每個面具都有一個編号，主辦方會把此編号告訴拿該面具的人。為了使舞會更有神秘感，主辦方把面具分為k (k≥3)類，并使用特殊的技術将每個面具的編号标在了面具上，隻有戴第i 類面具的人才能看到戴第i+1 類面具的人的編号，戴第k 類面具的人能看到戴第1 類面具的人的編号。

參加舞會的人并不知道有多少類面具，但是棟棟對此卻特别好奇，他想自己算出有多少類面具，于是他開始在人群中收集資訊。

棟棟收集的資訊都是戴第幾号面具的人看到了第幾号面具的編号。如戴第2号面具的人看到了第5 号面具。棟棟自己也會看到一些編号，他也會根據自己的面具編号把資訊補充進去。由于并不是每個人都能記住自己所看到的全部編号，是以，棟棟收集的信 息不能保證其完整性。現在請你計算，按照棟棟目前得到的資訊，至多和至少有多少類面具。由于主辦方已經聲明了k≥3，是以你必須将這條資訊也考慮進去。

Input

輸入第一行包含兩個整數n, m，用一個空格分隔，n 表示主辦方總共準備了多少個面具，m 表示棟棟收集了多少條資訊。

接下來m 行，每行為兩個用空格分開的整數a, b，表示戴第a 号面具的人看到了第b 号面具。相同的數對a, b 在輸入檔案中可能出現多次。

Output

輸出包含兩個數，第一個數為最大可能的面具類數，第二個數為最小可能的面具類數。如果無法将所有的面具分為至少3 類，使得這些資訊都滿足，則認為棟棟收集的資訊有錯誤，輸出兩個-1。

Sample Input

樣例1：

6 5

1 2

2 3

3 4

4 1

3 5

樣例2：

3 3

1 2

2 1

2 3

Sample Output

樣例1：

4 4

樣例2：

-1 -1

Hint

資料範圍：

50%的資料，滿足n ≤ 300, m ≤ 1000；

100%的資料，滿足n ≤ 100000, m ≤ 1000000。　

題解

orz QT666

出題直接出這種原題。。

考場各種yy，搞出了70分。。。

不亂說了，回歸正題。

歸結一下題意：

給定一張圖，每個點有一個編号 1..k

給定若幹條邊

邊一定是從編号 i 連向編号i+1，

且編号 K 連向編号1

求K的最大最小可能值

因為邊是單向，其實，圖一共就幾種情況：

1 .環

若幹個節點首位相連，那麼答案一定是目前環的長度的一個因數。

2.僞環

這個的處理和環是類似的，等下一起講。

僞環的形式大概是：

1---->2---->3---->4------
|                       |
|                       ↓
----------------------->5
           

3. 鍊

如果不存在環或者僞環，

那麼，最大的 K 值一定就是所有的鍊長之和

你可以想象為若幹鍊，然後把鍊首位相連，然後從1開始編号

接下來考慮如何處理環和僞環

對于僞環，我們可以考慮是一個邊向回走，

然後對應的編号再減少，

是以，存邊的時候，正邊邊權為1，反邊邊權為 −1

于是僞環也可以變成正環處理。

繼續想，怎麼計算答案，

因為最終的答案就是所有環的大小 gcd ，

求環的大小就是一遍 DFS

而環的大小的求法也不難，

首先給每個節點依次記錄從出發點開始的距離

如果目前點被第二次通路過，

那麼，環的大小就是 |dis−dis′|

而鍊的長度則是目前 DFS 出的最大的距離減去最小的距離

問題差不多解決了，關于 k≥3 的限制分類讨論即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 110000
inline int read()
{
    int x=,t=;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
    return x*t;
}
struct Line
{
    int v,next;
}e[MAX*];
int h[MAX],cnt=,n,m;
int M1,M2,M;
bool vis[MAX];
int ans=,dfn[MAX];
inline void Add(int u,int v)
{
    e[cnt]=(Line){v,h[u]};
    h[u]=cnt++;
}
int gcd(int a,int b)
{
    return !a?b:gcd(b%a,a);
}
void DFS(int u,int w)
{
    dfn[u]=w;vis[u]=true;
    M1=min(M1,w);M2=max(M2,w);
    for(int i=h[u];i!=-;i=e[i].next)
    {
        int v=e[i].v,ww=w+((i&)?-:);
        if(!vis[v])
        {
            DFS(v,ww);
        }
        else
            ans=gcd(ans,abs(dfn[v]-ww));
    }
}
int main()
{
    memset(h,-,sizeof(h));
    n=read();m=read();
    for(int i=;i<=m;++i)
    {
        int u=read(),v=read();
        Add(u,v);Add(v,u);
    }
    for(int i=;i<=n;++i)
        if(!vis[i])
        {
            DFS(i,);
            M+=M2-M1+;
            M2=M1=;
        }
    if(ans>=)
    {
        printf("%d ",ans);
        for(int i=;i<=ans;++i)
            if(ans%i==)
            {
                printf("%d\n",i);
                return ;
            }
    }
    if(ans==&&M>=)
    {
        printf("%d 3\n",M);
        return ;
    }
    puts("-1 -1");
    return ;
}