强连通+缩点
要被气死 一道题错了十来遍 有必要写个博客了
题目
https://loj.ac/p/10093
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#include<stack>
#include<vector>
vector<int>vik[1100];
int dfn[10100],low[10000],book[11000],time=0;
stack<int>s;
int ans=0,g[11100],out[10010],in[10010];
void tarjan(int x)
{
low[x]=dfn[x]=++time;
s.push(x);
book[x]=1;
for(int i=0; i<vik[x].size(); i++)
{
int h=vik[x][i];
if(!dfn[h])
{
tarjan(h);
low[x]=min(low[x],low[h]);
}
else if(book[h])//!!!!!!! 就错在这里 之前的代码没有加if后面的判断 一直过不去 还是翻了之前的代码发现以前也是这个错误一直过不去
//让我来思考一下为什么不加这个条件过不去 在这里是h点已经搜索过了 如果没有搜过那他的low和dfn都为0 直接赋值肯定是不对的 所以有个前提条件是h这个点已经被搜索过了
// 我们才能进行下面的赋值语句
low[x]=min(low[x],dfn[h]);
}
if(low[x]==dfn[x])
{
book[x]=0;
ans++;
int u;
do
{
u=s.top();
book[u]=0;
g[u]=ans;
s.pop();
}
while(u!=x);
}
}
int main()
{
int i,j,k,m,n;
scanf("%d",&n);
for(i=1;i<+n;i++)
vik[i].clear();
for(i=1; i<=n; i++)
{
while(~scanf("%d",&m)&&m)
{
vik[i].push_back(m);
}
}
for(i=1; i<=n; i++)
{
if(!dfn[i])
tarjan(i);
}
for(i=1; i<=n; i++)
{
for(j=0; j<vik[i].size(); j++)
{
int h=vik[i][j];
if(g[i]!=g[h])
{
out[g[i]]++;
in[g[h]]++;
}
}
}
int sum=0,b=0;
for(i=1; i<=ans; i++)
{
if(in[i]==0)
sum++;
if(out[i]==0)
b++;
}
if(ans==1)
{
printf("1\n");
printf("0\n");
return 0;
}
printf("%d\n%d\n",sum,max(sum,b));
return 0;
}#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#include<stack>
#include<vector>
vector<int>vik[1100];
int dfn[10100],low[10000],book[11000],time=0;
stack<int>s;
int ans=0,g[11100],out[10010],in[10010];
void tarjan(int x)
{
low[x]=dfn[x]=++time;
s.push(x);
book[x]=1;
for(int i=0; i<vik[x].size(); i++)
{
int h=vik[x][i];
if(!dfn[h])
{
tarjan(h);
low[x]=min(low[x],low[h]);
}
else if(book[h])//!!!!!!! 就错在这里 之前的代码没有加if后面的判断 一直过不去 还是翻了之前的代码发现以前也是这个错误一直过不去
//让我来思考一下为什么不加这个条件过不去 在这里是h点已经搜索过了 如果没有搜过那他的low和dfn都为0 直接赋值肯定是不对的 所以有个前提条件是h这个点已经被搜索过了
// 我们才能进行下面的赋值语句
low[x]=min(low[x],dfn[h]);
}
if(low[x]==dfn[x])
{
book[x]=0;
ans++;
int u;
do
{
u=s.top();
book[u]=0;
g[u]=ans;
s.pop();
}
while(u!=x);
}
}
int main()
{
int i,j,k,m,n;
scanf("%d",&n);
for(i=1;i<+n;i++)
vik[i].clear();
for(i=1; i<=n; i++)
{
while(~scanf("%d",&m)&&m)
{
vik[i].push_back(m);
}
}
for(i=1; i<=n; i++)
{
if(!dfn[i])
tarjan(i);
}
for(i=1; i<=n; i++)
{
for(j=0; j<vik[i].size(); j++)
{
int h=vik[i][j];
if(g[i]!=g[h])
{
out[g[i]]++;
in[g[h]]++;
}
}
}
int sum=0,b=0;
for(i=1; i<=ans; i++)
{
if(in[i]==0)
sum++;
if(out[i]==0)
b++;
}
if(ans==1)
{
printf("1\n");
printf("0\n");
return 0;
}
printf("%d\n%d\n",sum,max(sum,b));
return 0;
}
记得加判断
|