[刷题笔记] [JSOI2010] 连通数

Description

Problem

由于题目太短我直接上图罢

Analysis

题目描述非常简单，但是直接爆搜肯定会TLE，毕竟 \(n\leq 2000\)并且time limit=300ms。

我们发现如果题目保证无环直接topsort即可，问题就在环上，如何处理环呢？

我们可以缩点，缩点笔记，显然我们只需要统计答案数，缩完点后就变成了一个DAG，在DAG上跑topsort，统计答案统计上两个强连通分量祖先的儿子数乘积即可，显然若一个强连通分量祖先可以到达另一个强连通分量祖先，那么它们的儿子一定互相可达。

至于如何判断一个强连通分量可以到达另一个强连通分量呢？上文提到显然可以topsort，在topsort的时候可以开一个bitset优化一下，显然两个强连通分量祖先之间的关系要么为0要么为1（可达or不可达），直接bitset做运算继承关系即可。如果看起来很抽象见代码。

本题思路就这么简单，实现的时候需要注意很多细节。A了这道题，我对缩点有了更深刻的认识呢qwq

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
#include <stack>
using namespace std;
const int N=20500,M=4000500;
int n;
vector <int> Edge[N];
int dfn[N],low[N];
int cnt = 0;
int in_stack[N];
stack <int> s;
int vis[N];
int fa[N];
int fa_cnt = 0;
int fa_num[N];
bitset <N> new_map[N]; //bitset继承两个强连通分量祖先的关系
vector <int> new_Edge[N];
int ans = 0;
int in[N];
int v[N];
inline int read(){
    register int x = 0, t = 1;
    register char ch=getchar(); 
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);  
        ch=getchar();
    }
    return x*t;
}
inline void write(int x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}
int gc(){
    int x=getchar();
    if(x!='0'&&x!='1'){
        return gc();
    }
    else{
        return x;
    }
}
void Tarjan(int pos)
{
    dfn[pos] = low[pos] = ++cnt;
    v[pos] = 1;
    in_stack[pos] = 1;
    s.push(pos);
    for(int i=0;i<Edge[pos].size();i++)
    {
        if(!dfn[Edge[pos][i]])
        {
            Tarjan(Edge[pos][i]);
            low[pos] = min(low[pos],low[Edge[pos][i]]);
        }
        else if(in_stack[Edge[pos][i]])
        {
            low[pos] = min(low[pos],dfn[Edge[pos][i]]);
        }
    }
    if(dfn[pos] == low[pos])
    {
        fa_cnt ++;
        while(s.top() != pos)
        {
            fa_num[fa_cnt] ++;
            v[s.top()] = 0;
            fa[s.top()] = fa_cnt;
            in_stack[s.top()] = 0;
            s.pop();
        }
        s.pop();
        fa_num[fa_cnt] ++;
        fa[pos] = fa_cnt;
        in_stack[pos] = 0;
        new_map[fa_cnt][fa_cnt] = 1; //显然每个祖先自己一定可以到达自己
    }
}
void topsort()
{
    queue <int> q; //使用队列进行topsort
    for(int i=1;i<=fa_cnt;i++)
    {
        if(!in[i]) q.push(i);
    }
    while(!q.empty())
    {
        int noww = q.front();
        q.pop();
        for(int i=0;i<new_Edge[noww].size();i++)
        {
            new_map[new_Edge[noww][i]] |= new_map[noww]; //继承关系，显然只要有一个点可以到达另一个点则它们都可以到达那个点
            in[new_Edge[noww][i]] --; //每个节点的入度
            if(!in[new_Edge[noww][i]]) q.push(new_Edge[noww][i]);
        }
    }
}
int main()
{
    n = read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) 
        {
            char flg=gc(); //奇怪的输入被卡了....
            if(flg=='1') Edge[i].push_back(j);
        }
    }
    for(int i=1;i<=n;i++) 
    {
        if(!dfn[i]) Tarjan(i); //我们不保证原图一定联通，需要以每个点为root进行Tarjan，这个前提显然是该节点没有被访问，因为如果被访问过则已经操作了
    }
    for(int i=1;i<=n;i++)
    {
       for(int j=0;j<Edge[i].size();j++)
       {
            if(fa[i] != fa[Edge[i][j]])  //建反图
            {
                bool can_push = true;
                for(int k=0;k<new_Edge[fa[Edge[i][j]]].size();k++)
                {
                    if(new_Edge[fa[Edge[i][j]]][k] == fa[i]) 
                    {
                        can_push = false;
                        break;
                    }
                }
                if(can_push)
                {
                    new_Edge[fa[Edge[i][j]]].push_back(fa[i]);
                    in[fa[i]] ++;
                }
            }
       }
    }
    topsort();
    for(int i=1;i<=fa_cnt;i++)
    {
        for(int j=1;j<=fa_cnt;j++)
        {
            if(new_map[i][j]) ans += fa_num[i]*fa_num[j];//统计答案
        }
    }
    write(ans);
    return 0;
}