首页 > 其他 > 详细

ZOJ 3795 Grouping

时间:2014-06-08 09:44:47      阅读:489      评论:0      收藏:0      [点我收藏+]


给n个人的年龄大小关系,问最少分几组使每个组里面人的年龄不能直接或间接的比较。

每个联通块里的人都得分到不同的组,缩点后找最长的链即答案

tarjian缩点+dp找最长路


Grouping

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 si is not smaller than the age of person ti. 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 si and ti. 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}


Author: LUO, Jiewei
Source: ZOJ Monthly, June 2014


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=100100;

typedef pair<int,int> 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: "<<scc<<endl;

    for(int i=1;i<=scc;i++) cout<<num[i]<<"--";
    cout<<endl;

    for(int i=1;i<=n;i++)
    {
        cout<<"DFN: "<<DFN[i]<<" , Low: "<<Low[i]<<"     "<<Belong[i]<<endl;
    }
    cout<<endl;
}
*/
Edge edge2[maxn*3];int Size2,Adj2[maxn];

void Add_Edge2(int u,int v)
{
    edge2[Size2].to=v;
    edge2[Size2].next=Adj2[u];
    Adj2[u]=Size2++;
}

void Rebuild()
{
    int a,b;
    Size2=0; memset(Adj2,-1,sizeof(Adj2));
    for(int i=0;i<m;i++)
    {
        a=bian[i].first; b=bian[i].second;
        if(Belong[a]==Belong[b]) continue;
        Add_Edge2(Belong[a],Belong[b]);
    }
}

int dp[maxn];

int dfs(int u)
{
    if(dp[u]) return dp[u];
    dp[u]=num[u];
    int mx=0;
    for(int i=Adj2[u];~i;i=edge2[i].next)
    {
        int v=edge2[i].to;
        mx=max(mx,dfs(v));
    }
    dp[u]=dp[u]+mx;
    return dp[u];
}

int doit()
{
    int ans=0;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=scc;i++)
    {
        if(!dp[i]) dp[i]=dfs(i);
    }
    for(int i=1;i<=scc;i++)
        ans=max(ans,dp[i]);
    return ans;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            Add_Edge(a,b);
            bian[i]=make_pair(a,b);
        }
        solve();
     //   debug();
        Rebuild();
        printf("%d\n",doit());
    }
    return 0;
}





ZOJ 3795 Grouping,布布扣,bubuko.com

ZOJ 3795 Grouping

原文:http://blog.csdn.net/ck_boss/article/details/28918205

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!