「UVa 11324」The Largest Clique

发表于 |
字数统计: 621 | 阅读时长 ≈ 3

给定一个有向图，找出一个子图使得对于该子图的任意两个点$u$,$v$,$u$可以到达$v$或$v$可以到达$u$,判断这样的最大子图的节点个数。

链接

登不了UVa，只能用洛谷的链接惹qwq
UVa 11324

题解

求出图中的强连通分量，缩点，变成DAG。每一个点给一个权值，权值设为每个强连通分量的结点数。最后用记忆化搜索给出最长路。
求最长路时写炸了，输入居然可以决定最长路的总权值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct edge{
    ll to,prev;
};
edge ed[150001],scc[150001];
ll test,tot,num,top,cnt,nc,ec,ans;
ll last[150001],sccLast[150001],dfn[150001],low[150001],ins[150001],belong[150001];
ll from[150001],to[150001],size[150001],dp[150001];
stack<ll>st;
inline void addEdge(ll from,ll to)
{
    ed[++tot].to=to;
    ed[tot].prev=last[from];
    last[from]=tot;
}
inline void addSCC(ll from,ll to)
{
    scc[++tot].to=to;
    scc[tot].prev=sccLast[from];
    sccLast[from]=tot;
}
inline void tarjan(ll node)
{
    dfn[node]=low[node]=++num;
    st.push(node),ins[node]=1;
    ll flag=0,to;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        to=ed[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[node]=min(low[node],low[to]);
        }
        else
        {
            if(ins[to])
            {
                low[node]=min(low[node],dfn[to]);
            }
        }
    }
    if(dfn[node]==low[node])
    {
        cnt++;
        ll nd;
        do
        {
            nd=st.top(),st.pop();
            ins[nd]=0;
            belong[nd]=cnt;
            size[cnt]++;
        }
        while(node!=nd);
    }
}
inline void mergePoint()
{
    tot=0;
    for(register int i=0;i<ec;i++)
    {
        if(belong[from[i]]!=belong[to[i]])
        {
            addSCC(belong[from[i]],belong[to[i]]);
        }
    }
}
inline void search(ll node)
{
    if(dp[node]) 
    {
    	return;
    }
    dp[node]=size[node];
    ll maxn=0;
    for(register int i=sccLast[node];i;i=scc[i].prev)
    {
        if(!dp[scc[i].to])
        {
        	search(scc[i].to);
        }
        maxn=max(maxn,dp[scc[i].to]);
    }
    dp[node]+=maxn;
}
int main()
{
    cin>>test;
    for(register int i=0;i<test;i++)
    {
    	cin>>nc>>ec;
        for(register int i=0;i<ec;i++)
        {
            cin>>from[i]>>to[i];
            addEdge(from[i],to[i]);
        }
        for(register int i=1;i<=nc;i++)
        {
            if(!dfn[i])
            {
                tarjan(i);
            }
        }
        mergePoint();
        for(register int i=1;i<=cnt;i++)
        {
        	if(!dp[i])
        	{
        		search(i);
        		ans=max(ans,dp[i]);
            }
        }
        cout<<ans<<endl;
        tot=num=top=cnt=nc=ec=ans=0;
        memset(last,0,sizeof(last));
        memset(sccLast,0,sizeof(sccLast));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(ins,0,sizeof(ins));
        memset(belong,0,sizeof(belong));
        memset(from,0,sizeof(from));
        memset(to,0,sizeof(to));
        memset(size,0,sizeof(size));
        memset(dp,0,sizeof(dp));
        for(register int i=0;i<150001;i++)
        {
            ed[i].prev=ed[i].to=scc[i].prev=scc[i].to=0;
        }
    }
}