[HNOI2008]神奇的国度

Time Limit:20000MS Memory Limit:165536K
Total Submit:150 Accepted:41
Case Time Limit:5000MS

Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人
A1A2…An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人
AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

Input

第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系.
接下来M行每行输入一对朋友

Output

输出一个整数，最少可以分多少队

Sample Input

Sample Output

Hint

一种方案(1,3)(2)(4)

Source
哎。。总算差不多做完HNOI2008了。。我真是个傻叉啊。。
这题当时就把我震惊了。。一点思路都没有。。最小染色数不是NP问题么？
后来看了AekdyCoin神牛的题解才明白这是个弦图。。所以有专门的算法。。
神牛已经说的很清楚了。。Orz！！！！！！！
Code：
#include <vector>
#include <cstdio>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
const int maxn=10000+10;
using namespace std;
typedef vector<int>::iterator it;
int n,m,cnt[maxn]={},c[maxn]={},hash[maxn]={};
bool v[maxn]={};
vector<int> E[maxn],ord;
int main()
{
    //freopen("in","r",stdin);
    scanf("%d%d",&n,&m);int s,t;
    while(m–)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
    rep(i,n)
    {
        int max=-1,t;
        rep(j,n)if(!v[j]&&cnt[j]>max)max=cnt[j],t=j;
        v[t]=true;tr(e,E[t])cnt[*e]++;
        ord.pb(t);
    }
    c[ord[0]]=1;
    for(int id=1;id<=n-1;id++)
    {
        int t=ord[id];
        tr(e,E[t])hash]=id;
        rep(i,n)if(hash[i+1]!=id){c[t]=i+1;break;}
    }
    int ans=0;rep(i,n)ans>?=c[i];
    printf("%dn",ans);
}

34 51 21 42 42 33 4