Ccf 201509-4 highway

Face

Problem DescriptionIn a country with n cities, in order to make the traffic between cities more convenient, the king of the country intends to build some highways between the cities. Due to financial constraints, the king intends to repair some of the cities in the first stage. One-way highway. Now, the ministers have helped the king to plan a highway. After looking at the plan, the king found that some cities can be reached directly by highway (without other cities) or indirectly (via one or more other cities), while others cannot. If City A can reach City B by highway, and City B can also reach City A by highway, the two cities are called convenient city pairs. The king wanted to know how many convenient cities were in the plans the ministers gave him.The first line of the input format input contains two integers, n, which represent the number of cities and one-way highways, respectively. The next m lines, two integers a, b in each line, indicate that city a has a one-way highway to city b.The output format outputs a line containing an integer representing the number of convenient city pairs. Sample input 5 5 1 2 twenty three 3 4 4 2 3 5Sample output3Sample description

The connections between cities are shown in the figure. There are 3 convenient city pairs, they are (2, 3), (2, 4), (3, 4), please note that (2, 3) and (3, 2) are regarded as the same convenient city pair. Review use case size and convention The first 30% of the evaluation cases satisfy 1 ≤ n ≤ 100, 1 ≤ m ≤ 1000; The first 60% of the evaluation cases satisfy 1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000; All evaluation cases satisfy 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000.

Analysis and ideas:

This question is to judge the logarithm of two interconnected points in the directed graph. When I first started doing it, I didn't learn the connected component algorithm. My Xia Ji eight pushed a result and there was no sample. I had to explode. Each point dfs, use a mp two-dimensional array to save a point can reach another point, mp[i][j]==1 means that i can reach j, so it searches for 60%, then After doing this, I went to the Internet to learn the taijan algorithm. I found that this question is the tarjan board problem, directly apply tarjan, and finally find a combination number for each strongly connected component.

Violent dfs60 points code:

#include<iostream>
#include<cstring>
#include<queue>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,x,n) for(int i=n-1;i>=x;i--)
using namespace std;
//head
typedef long long ll;
int n,m,a,b,cur;
short mp[10001][10001];
int head[10006],vis[10006];
struct Edge{int to,next;}edge[100006];
void addedge(){edge[cur].to=b;edge[cur].next=head[a];head[a]=cur++;}
ll bfs()
{
    ll cnt=0;
    queue<int>q;
    rep(i,1,n+1)
    {
        memset(vis,0,sizeof(vis));
        q.push(i);vis[i]=1;
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int j=head[x];j!=-1;j=edge[j].next)
            {
                int nx=edge[j].to;
                if(!vis[nx])
                {
                q.push(nx);vis[nx]=1;mp[i][nx]=1;
                if(mp[i][nx]==1&&mp[nx][i]==1)cnt++;
                }
            }
        }
    }
    return cnt;
}
int main()
{
     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     memset(head,-1,sizeof(head));
     cin>>n>>m;
     rep(i,0,m)cin>>a>>b,addedge();
     cout<<bfs()<<endl;
     return 0;
}

Tarjan algorithm out of code:

#include<iostream>
#include<cstring>
#include<stack>
#define rep(i,x,n) for(int i=x;i<n;i++)
using namespace std;
int n, m, a, b, cnt, cur = 0, tot = 0, ans=0,head[10006], low[10006], dfn[10006],vis[10006];
struct Edge {
    int to, next;
} edge[100006];
void addedge() {
    edge[cur].to = b;
    edge[cur].next = head[a];
    head[a] = cur++;
}
stack<int>q;
int tarjan(int x) {
    low[x] = dfn[x] = ++tot;
    q.push(x);vis[x]=1;
    for(int i = head[x]; i != -1; i = edge[i].next) {
        int nx = edge[i].to;
        if(!dfn[nx]) {
            tarjan(nx);
            low[x] = min(low[x], low[nx]);
        } else if(vis[nx])
            low[x] = min(low[x], dfn[nx]);
    }
    if(low[x]==dfn[x])
    {
        cnt=0;
        while(1)
        {
            int tmp=q.top();
            q.pop();
            vis[tmp]=0;
            ++cnt;
            if(tmp==x)break;
        }
        if(cnt>1)ans+=(cnt*(cnt-1)/2);
    }
}
int main() {
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    rep(i, 0, m)cin >> a >> b, addedge();
    rep(i,1,n+1)if(!dfn[i])tarjan(i);
    cout << ans << endl;
}