P3387 【模板】缩点

分三部分：
1.使用tarjan缩点，将各个强连通分量(分量内各店可相互到达)看作一个点。
2.建立缩点后的拓扑图，这些连通分量间也存在连线。
3.由于tarjan的出栈操作，当dfn==low是出栈被标记，标记值是由小到大的。先被标记的值小。
因此要在拓扑图上逆序dp

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
vector<int>e[N],ne[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
int n,m,a[N],val[N],dp[N];
void tarjan(int x)
{
    //盖戳、入栈
    dfn[x]=low[x]=++tot;
    stk[++top]=x,instk[x]=1;
    for(int y:e[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            //回x时及时更新low
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) //若x已访问且在栈中
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) //若x时SCC的根
    {
        int y;++cnt;
        do{
            y=stk[top--];instk[y]=0; //出栈
            scc[y]=cnt; //SCC编号
            ++siz[cnt];
            val[cnt]+=a[y];
        }while(y!=x);
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    //建立拓扑图
    for(int i=1;i<=n;i++)
    {
        for(int j:e[i])
        {
            int a=scc[i],b=scc[j];
            if(a!=b) ne[a].push_back(b);
        }
    }
    //在拓扑图上逆序dp
    for(int x=cnt;x;x--)
    {
        if(dp[x]==0) dp[x]=val[x];
        for(int y:ne[x])
            dp[y]=max(dp[y],dp[x]+val[y]);
    }
    int ans=0;
    for(int i=1;i<=cnt;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
}
signed main()
{
    solve();
    return 0;
}




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

P3388 【模板】割点（割顶）

割点判定法则： low[y]>=dfn[x]
非根结点找到一颗子树，根节点至少需要两棵子树。

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
vector<int>e[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int cut[N],root;
int n,m;
void tarjan(int x)
{
    //盖戳、入栈
    dfn[x]=low[x]=++tot;
    int child=0;
    for(int y:e[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            //回x时及时更新low,判断割点
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                child++;
                if(x!=root||child>1)
                    cut[x]=1;
            }
        }
        else  
            low[x]=min(low[x],dfn[y]);
    }
    
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) 
            root=i,tarjan(i);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(cut[i]) ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        if(cut[i]) cout<<i<<" ";
    cout<<endl;
}
signed main()
{
    solve();
    return 0;
}




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

割边

https://www.bilibili.com/video/BV14g411Q7ze?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8
条件：low[y]>dfn[x] 不允许走x->y的反边更新low值

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
#define ULL unsigned long long
using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
const int P=131;
struct edge
{
    int to,nxt;
}e[N];  //边集
int dfn[N],low[N],tot,cnt,idx=1;
struct bridge
{
    int x,y;
}bri[N];
void add(int to,int nxt)
{
    e[++idx]={to,head[from]};
    h[from]=idx;
}
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++tot;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
            bri[++cnt]={x,y};
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}

void solve()
{
    
}
signed main()
{
    solve();
    return 0;
}

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

P7687 [CEOI2005] Critical Network Lines

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
#define ULL unsigned long long
using namespace std;
const int N=7e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
const int P=131;
struct edge
{
    int to,nxt;
}e[N];  //边集
int dfn[N],low[N],tot,cnt,idx=1,head[N],a[N],b[N],n,m,k,l;
struct bridge
{
    int x,y;
}bri[N];
void add(int from,int to)
{
    e[++idx]={to,head[from]};
    head[from]=idx;
}
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++tot;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
            {
                if(!a[y]||!b[y]||a[y]==k||b[y]==l)
                    bri[++cnt]={x,y};
            }
            a[x]+=a[y],b[x]+=b[y];
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}

void solve()
{
    cin>>n>>m>>k>>l;
    for(int i=1,x;i<=k;i++)
        cin>>x,a[x]=1;
    for(int i=1,x;i<=l;i++)
        cin>>x,b[x]=1;
    for(int i=1,u,v;i<=m;i++)
    {
        cin>>u>>v;add(u,v),add(v,u);
    }
    tarjan(1,2);
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
        cout<<bri[i].x<<" "<<bri[i].y<<endl;
}
signed main()
{
    solve();
    return 0;
}




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

字符串哈希

P3370 【模板】字符串哈希

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
#define ULL unsigned long long
using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
const int P=131;
ULL p[N],h[N];
int n,a[N];
char s[N];
int init(char s[])
{
    p[0]=1,h[0]=0;
    int len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
    return h[len];
}
//计算s[l-r]之间的hash值
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
//判断两子串是否相同
bool subs(int l1,int r1,int l2,int r2)
{
    return get(l1,r1)==get(l2,r2);
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        a[i]=init(s);
    }
    int ans=1;
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++)
        if(a[i]!=a[i-1]) ans++;
    cout<<ans<<endl;
}
signed main()
{
    solve();
    return 0;
}




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