【题意】给定n个点的有向图，求可达点对数（互相可达算两对，含自身）。n<=2000。

【算法】强连通分量(tarjan)+拓扑排序+状态压缩(bitset)

【题解】这题可以说非常经典了。

1.强连通分量(scc)内所有点可互达，对答案的贡献为cnt[i]*cnt[i](cnt[i]第i个scc内点的个数)。

2.缩点得到新图，对新图中的每一个点开一个bitset[2000]来记录第i个点能否到达它，初始值为f[i][i]=1。

bitset用法：http://blog.163.com/lixiangqiu_9202/blog/static/53575037201251121331412/

（DAG和树不同，x到y会有多条路径，所以不能简单的记录数值而是要记录状态来合并，因为信息不可重，这里bitset的使用非常经典）

3.按拓扑序进行递推，f[y]|=f[x](edge x→y)

4.f[i][j]==1时ans+=cnt[i]*cnt[j]。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=2010,maxm=5000010;struct edge{
    int u,v,from;}e[maxm],e1[maxm];int n,tot,tot1,first[maxn],first1[maxn],dfn[maxn],low[maxn],mark,s[maxn],lack[maxn],color,col[maxn],num[maxn],top,in[maxn];char st[2010];bitset
           
            f[maxn];queue
            
             q;void insert(int u,int v){tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void insert1(int u,int v){tot1++;e1[tot1].u=u;e1[tot1].v=v;e1[tot1].from=first1[u];first1[u]=tot1;in[v]++;}void tarjan(int x){ dfn[x]=low[x]=++mark; s[++top]=x;lack[x]=top; for(int i=first[x];i;i=e[i].from) { int y=e[i].v; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(!col[y])low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { color++; for(int i=lack[x];i<=top;i++)col[s[i]]=color; num[color]=top-lack[x]+1; top=lack[x]-1; }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",st); for(int j=0;j