「CF506B」Mr. Kitayuta’s Technology

2015年1月19日5,3410

Shuseki Kingdom is the world’s leading nation for innovation and technology. There are n cities in the kingdom, numbered from 1 to n.

Thanks to Mr. Kitayuta’s research, it has finally become possible to construct teleportation pipes between two cities. A teleportation pipe will connect two cities unidirectionally, that is, a teleportation pipe from city x to city ycannot be used to travel from city y to city x. The transportation within each city is extremely developed, therefore if a pipe from city x to city y and a pipe from city y to city z are both constructed, people will be able to travel from city x to city z instantly.

Mr. Kitayuta is also involved in national politics. He considers that the transportation between the m pairs of city(a_i, b_i) (1 ≤ i ≤ m) is important. He is planning to construct teleportation pipes so that for each important pair(a_i, b_i), it will be possible to travel from city a_i to city b_i by using one or more teleportation pipes (but not necessarily from city b_i to city a_i). Find the minimum number of teleportation pipes that need to be constructed. So far, no teleportation pipe has been constructed, and there is no other effective transportation between cities.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵), denoting the number of the cities in Shuseki Kingdom and the number of the important pairs, respectively.

The following m lines describe the important pairs. The i-th of them (1 ≤ i ≤ m) contains two space-separated integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), denoting that it must be possible to travel from city a_i to city b_i by using one or more teleportation pipes (but not necessarily from city b_i to city a_i). It is guaranteed that all pairs (a_i, b_i)are distinct.

Output

Print the minimum required number of teleportation pipes to fulfill Mr. Kitayuta’s purpose.

Sample test(s)

input

4 5

1 2

1 3

1 4

2 3

2 4

output

3

input

4 6

1 2

1 4

2 3

2 4

3 2

3 4

output

4

Note

For the first sample, one of the optimal ways to construct pipes is shown in the image below:

$\text{[math]}$ For the second sample, one of the optimal ways is shown below:

$\text{[math]}$

结论题TAT

一个弱连通块中没有环的话那么对答案的贡献就是该连通块中点数-1

否则为点的个数

缩环后用并查集维护一下即可

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<bitset>
#define inf 2000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans,cnt,ind,top,scc;
int low[100005],dfn[100005],q[100005],bl[100005],num[100005];
int fa[100005],last[100005];
bool inq[100005],mark[100005];
struct edge{
    int to,next,v;
}e[100005];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void tarjan(int x)
{
    low[x]=dfn[x]=++ind;
    inq[x]=1;q[++top]=x;
    for(int i=last[x];i;i=e[i].next)
        if(!dfn[e[i].to])
        {
            tarjan(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
        }
        else if(inq[e[i].to])
            low[x]=min(low[x],dfn[e[i].to]);
    if(low[x]==dfn[x])
    {
        int now=0;scc++;
        while(x!=now)
        {
            now=q[top];top--;
            bl[now]=scc;
            inq[now]=0;
            num[scc]++;
            if(num[scc]!=1)mark[scc]=1;
        } 
    }
}
void rebuild()
{
    cnt=0;
    for(int x=1;x<=n;x++)
    {
        for(int i=last[x];i;i=e[i].next)
            {
                int u=bl[x],v=bl[e[i].to];
                int p=find(u),q=find(v);
                if(p!=q)
                {
                    fa[p]=q;num[q]+=num[p];mark[q]|=mark[p];
                }
            }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        insert(u,v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=scc;i++)fa[i]=i;
    rebuild();
    for(int i=1;i<=scc;i++)
        if(fa[i]==i)
        {
            if(!mark[i])ans+=num[i]-1;
            else ans+=num[i];
        }
    printf("%d\n",ans);
    return 0;
}

#include<iostream>

#include<set>

#include<map>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<cmath>

#include<bitset>

#define inf 2000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans,cnt,ind,top,scc;

int low[100005],dfn[100005],q[100005],bl[100005],num[100005];

int fa[100005],last[100005];

bool inq[100005],mark[100005];

struct edge{

int to,next,v;

}e[100005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

int find(int x)

{

return x==fa[x]?x:fa[x]=find(fa[x]);

}

void tarjan(int x)

{

low[x]=dfn[x]=++ind;

inq[x]=1;q[++top]=x;

for(int i=last[x];i;i=e[i].next)

if(!dfn[e[i].to])

{

tarjan(e[i].to);

low[x]=min(low[x],low[e[i].to]);

}

else if(inq[e[i].to])

low[x]=min(low[x],dfn[e[i].to]);

if(low[x]==dfn[x])

{

int now=0;scc++;

while(x!=now)

{

now=q[top];top--;

bl[now]=scc;

inq[now]=0;

num[scc]++;

if(num[scc]!=1)mark[scc]=1;

}

void rebuild()

{

cnt=0;

for(int x=1;x<=n;x++)

{

for(int i=last[x];i;i=e[i].next)

{

int u=bl[x],v=bl[e[i].to];

int p=find(u),q=find(v);

if(p!=q)

{

fa[p]=q;num[q]+=num[p];mark[q]|=mark[p];

}

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

}

for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);

for(int i=1;i<=scc;i++)fa[i]=i;

rebuild();

for(int i=1;i<=scc;i++)

if(fa[i]==i)

{

if(!mark[i])ans+=num[i]-1;

else ans+=num[i];

}

printf("%d\n",ans);

return 0;

}

« 「CF500E」New Year Domino 「BZOJ1370」[Baltic2003] Gang团伙 »

hzwer.com _ Home | http://hzwer.com

「CF506B」Mr. Kitayuta’s Technology

分类目录

热门文章

Myfriends

近期评论