ZOJ 3795 Grouping

給n個人的年齡大小關系,問最少分幾組使每個組裡面人的年齡不能直接或間接的比較。

每個聯通塊裡的人都得分到不同的組，縮點後找最長的鏈即答案

tarjian縮點+dp找最長路

Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The i-th message shows that the age of person s_i is not smaller than the age of person t_i. Now we need to divide all these N people into several groups. One's age shouldn't be compared with each other in the same group, directly or indirectly. And everyone should be assigned to one and only one group. The task is to calculate the minimum number of groups that meet the requirement.

Input

There are multiple test cases. For each test case: The first line contains two integers N(1≤ N≤ 100000), M(1≤ M≤ 300000), N is the number of people, and M is is the number of messages. Then followed by M lines, each line contain two integers s_i and t_i. There is a blank line between every two cases. Process to the end of input.

Output

For each the case, print the minimum number of groups that meet the requirement one line.

Sample Input

4 4
1 2
1 3
2 4
3 4

Sample Output

3

Hint

set1= {1}, set2= {2, 3}, set3= {4}

#include 
#include 
#include 
#include 

using namespace std;

const int maxn=100100;

typedef pair pII;

struct Edge
{
    int to,next;
}edge[maxn*3];

pII bian[maxn*3];

int Adj[maxn],Size;
int n,m;

void init()
{
    Size=0;memset(Adj,-1,sizeof(Adj));
}

void Add_Edge(int u,int v)
{
    edge[Size].to=v;
    edge[Size].next=Adj[u];
    Adj[u]=Size++;
}

int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn],num[maxn];
int Index,top,scc;
bool Instack[maxn];

void tarjan(int u,int fa)
{
    int v;
    Low[u]=DFN[u]=++Index;
    Stack[top++]=u;
    Instack[u]=true;

    for(int i=Adj[u];~i;i=edge[i].next)
    {
        v=edge[i].to;
       // if(v==fa) continue;
        if(!DFN[v])
        {
            tarjan(v,u);
            Low[u]=min(Low[u],Low[v]);
        }
        else if(Instack[v])
        {
            Low[u]=min(Low[u],DFN[v]);
        }
    }

    if(Low[u]==DFN[u])
    {
        scc++;
        do
        {
            v=Stack[--top];
            Instack[v]=false;
            num[scc]++;
            Belong[v]=scc;
        }while(v!=u);
    }
}

void solve()
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,0,sizeof(Instack));
    memset(num,0,sizeof(num));

    Index=scc=top=0;

    for(int i=1;i<=n;i++)
    {
        if(!DFN[i]) tarjan(i,i);
    }
}
/*
void debug()
{
     cout<<"scc: "<