首页 > 其他 > 详细

The Largest Clique

时间:2014-03-29 05:24:18      阅读:431      评论:0      收藏:0      [点我收藏+]

题目链接

  • 题意:
    给定一张有向图G,求一个节点数最大的节点集,使得该节点集中任意两个节点u和v满足:要么u可以到达v,要么v可以到达u(相互到达也可以)
    输入:测试组数T;第一行节点数n和边数m;m行每行两个整数表示一条有向边,点从1编号
  • 分析:
    观察这个特点,那么对于原图中存在的强连通分量,肯定是满足题意的。那么接下来就是缩点,之后的图就是若干个DAG。求节点数最多的路径,也就是在DAG上找一个最长的路径,可以用DP或者记忆化搜索来,以下采用编码简单的记忆化搜索
  • 重点:
    缩点得到DAG
    在DAG上的记忆化搜索
    因为scc_cnt是从1开始的,初始化时候需要注意
//有向图的强连通分量
//每次调用前手动清空vector<int> G
//使用时只更新G完成构图
//scc_cnt从1开始计数

//pre[]表示点在DFS树中的先序时间戳
//lowlink[]表示当前点和后代能追溯到的最早祖先的pre值
//sccno[]表示点所在的双连通分量编号
//vector<int> G保存每个点相邻的下一个点序号
//stack<Edge> S是算法用到的栈
const int MAXV = 1100;

vector<int> G[MAXV];
int pre[MAXV], lowlink[MAXV], sccno[MAXV], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u])
    {
        scc_cnt++;
        for(;;)
        {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}

void find_scc(int n)
{
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for(int i = 0; i < n; i++)
        if(!pre[i]) dfs(i);
};

int num[MAXV], in[MAXV], ans[MAXV];
vector<int> vt[MAXV];

int search(int u)
{
    if (ans[u]) return ans[u];
    int ret = 0;
    REP(i, vt[u].size())
    {
        int v = vt[u][i];
        ret = max(ret, search(v));
    }
    return ans[u] = num[u] + ret;
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int T, n, m, a, b;
    RI(T);
    REP(kase, T)
    {
        RII(n, m);
        REP(i, n + 1)
        {
            G[i].clear();
            vt[i].clear();
        }
        CLR(num, 0);
        CLR(in, 0);
        CLR(ans, 0);

        REP(i, m)
        {
            RII(a, b); a--; b--;
            G[a].push_back(b);
        }
        find_scc(n);
        REP(i, n)
        {
            num[sccno[i]]++;
            int u = i;
            REP(j, G[i].size())
            {
                int v = G[i][j];
                if (sccno[u] != sccno[v])
                {
                    vt[sccno[u]].push_back(sccno[v]);
                    in[sccno[v]]++;
                }
            }
        }
        int ans = 0;
        FE(i, 1, scc_cnt)
        {
            if (in[i] == 0)
                ans = max(ans, search(i));
        }
        WI(ans);
    }
    return 0;
}


The Largest Clique,布布扣,bubuko.com

The Largest Clique

原文:http://blog.csdn.net/wty__/article/details/22401075

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