# 179 条题解

• @ 2017-10-02 17:27:08

Accepted

# 状态 耗时 内存占用

#1 Accepted 3ms 440.0 KiB
#2 Accepted 2ms 436.0 KiB
#3 Accepted 2ms 308.0 KiB
#4 Accepted 2ms 324.0 KiB
#5 Accepted 3ms 428.0 KiB
#6 Accepted 2ms 436.0 KiB
#7 Accepted 1ms 444.0 KiB
#8 Accepted 1ms 452.0 KiB
#9 Accepted 2ms 424.0 KiB
#10 Accepted 1ms 444.0 KiB

#include <bits/stdc++.h>
using namespace std;

const int maxn = 210;
int n, cmp[maxn];
bool vis[maxn];
vector<int> G[maxn], rG[maxn], vs;

void add_edge(int u, int v) {
G[u].push_back(v);
rG[v].push_back(u);
}

void dfs(int u) {
vis[u] = true;
for (int v : G[u]) {
if (!vis[v]) {
dfs(v);
}
}
vs.push_back(u);
}

void rdfs(int u) {
vis[u] = true;
for (int v : rG[u]) {
if (!vis[v]) {
dfs(v);
}
}
}

int kosaraju() {
memset(vis, false, sizeof(vis));
vs.clear();
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
}
}
memset(vis, false, sizeof(vis));
int k = 0;
for (int i = vs.size() - 1; i >= 0; i--) {
if (!vis[vs[i]]) {
k++;
dfs(vs[i]);
}
}
return k;
}

int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int u = 1, v; u <= n; u++) {
while (cin >> v && v != 0) {
}
}
cout << kosaraju() << endl;
return 0;
}

• @ 2019-05-17 14:12:00

tarjan的注意，图的大小要开到n的平方，不然会炸（其实10000就够）

• @ 2018-08-14 13:52:49
#include<bits/stdc++.h>
using namespace std;
const int maxn=204,maxm=40004;
int n,sum=0,dep=0,cnt=0;
stack<int>s;
struct node{
int to,next;
}e[maxm];
}
void tarjan(int u){
vis[u]=1;
dfn[u]=low[u]=++dep;
s.push(u);
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
col[u]==++sum;vis[u]=0;
while(1){
int x=s.top();
s.pop();
col[x]=sum;
vis[x]=0;
if(u==x) break;
}
}
}
void shrink_point(){
for(int i=1;i<=n;i++){
int v=e[j].to;
if(col[i]==col[v]) continue;
in[col[v]]++;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
while(cin>>x){
if(x==0) break;
}
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
shrink_point();
int ans=0;
for(int i=1;i<=sum;i++)
if(!in[i]) ans++;
cout<<ans;
}

• @ 2017-06-29 08:56:23

Accepted

# 状态 耗时 内存占用

#1 Accepted 3ms 360.0KiB
#2 Accepted 1ms 328.0KiB
#3 Accepted 3ms 384.0KiB
#4 Accepted 4ms 256.0KiB
#5 Accepted 3ms 200.0KiB
#6 Accepted 3ms 256.0KiB
#7 Accepted 3ms 256.0KiB
#8 Accepted 4ms 256.0KiB
#9 Accepted 1ms 332.0KiB
#10 Accepted 1ms 332.0KiB
本来想用一下简便方法，结果爆零，只好老老实实打了一遍Tarjan。
#include<cstdio>
#include<iostream>
using namespace std;
struct node{
int from,to,next;
}e[10010];
int v[250],book[250],dfn[250],low[250],s[250],father[250],rd[250],
flag[250],n,m,l,r,index=0,tot=0,top=0,ans=0,count=0,M=0;
void tarjan(int x){
book[x]=1;
s[++top]=x;
dfn[x]=low[x]=++index;
for(int j=v[x];j;j=e[j].next){
if(!book[e[j].to]){
tarjin(e[j].to);
if(low[x]>low[e[j].to])
low[x]=low[e[j].to];
}
else if(!flag[e[j].to])
if(low[x]>dfn[e[j].to])low[x]=dfn[e[j].to];
}

if(dfn[x]==low[x]){
count++;
while(s[top+1]!=x){
father[s[top]]=count;
flag[s[top--]]=1;
}
}
return;
}
e[++tot].from=x;
e[tot].to=y;
e[tot].next=v[x];
v[x]=tot;
return;
}
void in(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
while(m!=0){
M++;
cin>>m;
}
}
return;
}
int main(){
in();
for(int i=1;i<=n;i++)
if(!book[i])tarjan(i);
for(int i=1;i<=M;i++)
if(father[e[i].from]!=father[e[i].to])
rd[father[e[i].to]]++;
for(int i=1;i<=count;i++)
if(!rd[i])ans++;
cout<<ans;
return 0;
}

• @ 2017-06-29 08:59:36

差评

• @ 2019-01-29 20:52:36

# include<bits/stdc++.h>

using namespace std;

struct{
int from,too,next;
}edge[40010];

int ans,top,m,num;

bool flag[210],ru[210][210];

ans++;
edge[ans].from=x;
edge[ans].too=y;
}

void tarjan(int k){
num++;
dfn[k]=num;
low[k]=num;
flag[k]=true;
Q[++top]=k;
int u=edge[i].too;
if (!dfn[u]){
tarjan(u);
low[k]=min(low[k],low[u]);
}
else{
if (flag[u]) low[k]=min(low[k],dfn[u]);
}
}
if (low[k]==dfn[k]){
inwhich[k]=++m;
flag[k]=false;
while(1){
int x=Q[top--];

inwhich[x]=m;
flag[x]=false;
if (k==x) break;
}
}
}

int main()
{
int n;
cin>>n;
int x;
for (int i=1;i<=n;i++){
int x;
cin>>x;
while (x!=0){
cin>>x;
}
}
for (int i=1;i<=n;i++){
if (!dfn[i]) tarjan(i);
}
for (int i=1;i<=n;i++){
int v=edge[j].too;
if (inwhich[v]==inwhich[i]) continue;
rudu[inwhich[v]]++;
}
}
int ansn=0;
for (int i=1;i<=m;i++)
if (rudu[i]==0) ansn++;
cout<<ansn;
return 0;
}

• @ 2017-10-20 20:21:28

一开始就以为是最简单的tarjian模板题，但是后来仔细读题发现并不是这样，问了同学，才A的。
大致就是强联通分量缩点之后，统计一遍入度为0的点，就是答案
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 214748364
#define DB double
using namespace std;
{
int x=0,w=1;char ch=0;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;

}
int tot,n,h[10000],H[10000],totA;
struct po{
int u,v,c,last;
}a[10000],A[10000];
int ans;
int num[100000],T,dfn[10000],low[10000];
int q[10000],l,in[10000],to[100000];
int R[10000];
{
tot++;
a[tot].v=v;
a[tot].last=h[u];
h[u]=tot;
}
{
totA++;
A[totA].v=v;
A[totA].last=H[u];
H[u]=totA;
}
void tarjian(int u)
{
dfn[u]=low[u]=++T;
in[u]=1;l++,q[l]=u;
for(int i=h[u];i;i=a[i].last)
{
int v=a[i].v;
if(!dfn[v])
{
tarjian(v);
low[u]=min(low[u],low[v]);

} else if(in[v]) low[u]=min(dfn[v],low[u]);
}
if(dfn[u]==low[u])
{
num[0]++;
do{
in[q[l]]=0;
to[q[l]]=num[0];
num[num[0]]++;
}while(q[l--]!=u);

}
}
int main()
{
for(int i=1;i<=n;i++)
{
int x;
while(scanf("%d",&x)!=EOF)
{
if(x==0) break;

}

}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjian(i);
for(int i=1;i<=tot;i++)
{
int u=a[i].u;int v=a[i].v;
if(to[u]==to[v]) continue;
R[to[v]]++;

}
for(int i=1;i<=num[0];i++)
{
if(R[i]==0) ans++;

}
printf("%d",ans);
return 0;
}

• @ 2017-06-29 09:00:57

老老实实用Tarjan，很容易，一道很简单的模拟题，，，
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,a,b,dfn[10001],low[10001],v[10001],shu=0,count=0,tot=0,vis[10001],s[10001],t=0,top=0,flag[10001],father[100001],ru[10001];
struct edge
{
int from,to,next;
}e[10001];
{
tot++;
e[tot].from=x;
e[tot].to=y;
e[tot].next=v[x];
v[x]=tot;
}
/*int find(int x)
{
if(father[x]!=x)return father[x]=find(father[x]);
return x;
}
void uni(int x,int y)
{
int r1=find(x),r2=find(y);
if(r1!=r2)father[r2]=r1;
}*/
void taj(int i)
{

dfn[i]=low[i]=++shu;
vis[i]=1;
s[++top]=i;
int j;
for(j=v[i];j;j=e[j].next)
{
int k=e[j].to;
if(!vis[k])
{
taj(k);
if(low[k]<low[i])low[i]=low[k];
}
else if(!flag[k])
{
if(low[i]>dfn[k])low[i]=dfn[k];
}
}
if(dfn[i]==low[i])
{
count++;
while(s[top+1]!=i)
{

flag[s[top]]=1;
father[s[top]]=count;
--top;

}
}

}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
if(a!=0)
while(a!=0)
{
cin>>a;
if(a!=0)
}

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

for(int i=1;i<=tot;i++)
{

if(father[e[i].from]!=father[e[i].to])ru[father[e[i].to]]++;
}
for(int i=1;i<=count;i++)
{
if(ru[i]==0)t++;
}
cout<<t;
return 0;
}

• @ 2017-05-07 12:56:17
/*
问一下这题和P1022有何区别
直接把题解搬过来了...OTZ
这题很明显是一个有向图模型~
同时是要求强连通分量的个数~！
因为n很小   所以完全可以用Floyd预处理
然后统计连通块
用并查集也很方便~
当然也可以写个标准一点的Tarjan统计SCC数量~
这里窝两个都写了一下
*/
/*
方法1:
Floyd判断连通性，最后注意统计连通块的方法：v数组
不再多说~
细节看代码就好
*/
/*#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

bool a[203][203];
bool v[203];
int n;
int m;
int tot;

void init()
{
int x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
while(scanf("%d",&x)==1&x)
a[i][x]=1;
}
}

void Floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][k]&&a[k][j])
a[i][j]=1;
}

void work()
{
for(int i=1;i<=n;i++)
if(!v[i])
{
for(int j=1;j<=n;j++)
if(a[i][j]&&a[j][i]&&!v[j])
v[j]=1;
tot++;
v[i]=1;
}
cout<<tot<<endl;
}

int main()
{
init();
Floyd();
work();
return 0;
}
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

const int MAXN=205;
const int MAXM=40005;
struct Edge
{
int to,next;
}e[MAXM];
int fisrt[MAXN];//Edges
int clock_cnt,scc_cnt;
int pre[MAXN],low[MAXN];
int sccno[MAXN];
stack<int> s;
int n,tot;

{
e[++tot].to=y;  e[tot].next=fisrt[x];   fisrt[x]=tot;
}

void init()
{
memset(fisrt,-1,sizeof(fisrt));
int v;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
while(scanf("%d",&v)==1&&v)
}
}

void dfs(int u)
{
pre[u]=low[u]=++clock_cnt;
s.push(u);
for(int i=fisrt[u];i!=-1;i=e[i].next)
{
int& v=e[i].to;
if(!pre[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else    if(!sccno[v])
low[u]=min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc_cnt++;
int x=0;
for(;;)
{
x=s.top();  s.pop();
sccno[x]=scc_cnt;
if(x==u)
break;
}
}
}

void Tarjan()
{
for(int i=1;i<=n;i++)
if(!pre[i])
dfs(i);
cout<<scc_cnt<<endl;
}

int main()
{
init();
Tarjan();
}

• @ 2017-04-20 22:02:44

#

状态

耗时

内存占用

#1  Accepted  2ms 340.0KiB
#2  Accepted  2ms 324.0KiB
#3  Accepted  3ms 376.0KiB
#4  Accepted  3ms 340.0KiB
#5  Accepted  2ms 344.0KiB
#6  Accepted  2ms 320.0KiB
#7  Accepted  3ms 320.0KiB
#8  Accepted  2ms 320.0KiB
#9  Accepted  3ms 336.0KiB
#10  Accepted  2ms 320.0KiB

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=205;
struct Edge {
int to,next;
} Edge[maxn*maxn];
cnt++;
Edge[cnt].to=to;
}
void Tarjan(int Now) {
step++;
Stack[++top]=Now;
Instack[Now]=1;
int Next=Edge[i].to;
if(!Dfn[Next]) {
Tarjan(Next);
}
SCC++;
int y;
do {
y=Stack[top--];
Belong[y]=SCC;
Instack[y]=0;
} while(y!=Now);
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x;
while(x=Get_Int()) {
if(x==0)break;
}
}
for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i);
for(int i=1; i<=n; i++)
if(Belong[i]!=Belong[Edge[j].to])InDegree[Belong[Edge[j].to]]++;
for(int i=1; i<=SCC; i++)
if(InDegree[i]==0)ans++;
printf("%d\n",ans);
return 0;
}

• @ 2017-03-08 00:03:49

楼下许多代码其实是错的。。。
反例：
5
2 0
3 0
4 0
5 0
0
Ans=1
正解：Tarjan建新图统计入度

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=205;
struct Edge {
int to,next;
} Edge[maxn*maxn];
cnt++;
Edge[cnt].to=to;
}
void Tarjan(int Now) {
step++;
Stack[++top]=Now;
Instack[Now]=1;
int Next=Edge[i].to;
if(!Dfn[Next]) {
Tarjan(Next);
}
SCC++;
int y;
do {
y=Stack[top--];
Belong[y]=SCC;
Instack[y]=0;
} while(y!=Now);
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x;
while(x=Get_Int()) {
if(x==0)break;
}
}
for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i);
for(int i=1; i<=n; i++)
if(Belong[i]!=Belong[Edge[j].to])InDegree[Belong[Edge[j].to]]++;
for(int i=1; i<=SCC; i++)
if(InDegree[i]==0)ans++;
printf("%d\n",ans);
return 0;
}

• @ 2017-02-18 16:43:26

为什么在JDFZoj 上提交有7%错误这里就是accepted呢

• @ 2017-02-18 16:21:22

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int point[10000];
int nex[10000],to[10000];
bool inloop[10000],noto[10000];
int ans=0;
void search(int n)
{
inloop[n]=false;
int side=point[n];
while(side!=0)
{
if(inloop[to[side]]==true)
search(to[side]);
side=nex[side];
}
}
int main()
{
memset(inloop,true,sizeof(inloop));
memset(point,0,sizeof(point));
memset(noto,true,sizeof(noto));
memset(nex,0,sizeof(nex));
cin>>n;
int m=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while(x!=0)//输入第m条边 i到x
{
m++;
nex[m]=point[i];
point[i]=m;
to[m]=x;
noto[x]=false;
scanf("%d",&x);
}
}
for(int i=1;i<=n;i++)//讨论并查集的头结点
{
if(noto[i]==true)
{
ans++;
search(i);
}
}
for(int i=1;i<=n;i++)//讨论有循环的情况
{
if(inloop[i]==true)
{
ans++;
search(i);
}
}
cout<<ans<<endl;
return 0;
}
并查集就可以了不用太复杂。

• @ 2017-01-02 20:42:51

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define f(i,j,k) for(int i=k;i<=j;i++)
#define d(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
struct node {
int zhi,nex;
}e[400000+5];
int cnt;
int dfn[404];
int low [404],stac[404],instack[404];
int numbe,belong[404],bcnt;
int top;
{
cnt++;
e[cnt].zhi=y;

}
void tarjan(int v) {
int u;
dfn[v] = low[v] = ++numbe;
instack[v] = true;
stac[++top] = v;
for (int i = head[v]; i ; i=e[i].nex) {
u = e[i].zhi;
if (!dfn[u]) {
tarjan(u);
if (low[u] < low[v])
low[v] = low[u];
}
else if (instack[u] && dfn[u] < low[v])
low[v] = dfn[u];
}
if (dfn[v] == low[v]) {
bcnt++;
do {
u = stac[top--];
instack[u] = false;
belong[u] = bcnt;
}
while (u != v);
}
}

bool se[404];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int m;
while(scanf("%d",&m)&&m)
{
}
}
for(int i=1;i<=n;i++)
{
if(!belong[i])
tarjan(i);
}
int ans=0;

for(int i=1;i<=n;i++)
{
int p=belong[i];
if(!p) ans++;
else {
if(!se[p]) ans++,se[p]=true;
}
}
printf("%d",ans);
return 0;
}

• @ 2016-11-19 18:46:34

1022 1023这两道题有毒啊

• @ 2016-11-17 13:37:04

强连通分量，很好的一道模板题
pascal
//
var a:array[0..201,0..201] of longint;
f,v:array[0..201] of boolean;
stack,dfn,low:array[0..1000] of longint;
x,i,n,ans,deep,d:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
procedure dfs(x:longint);
var i:integer;
begin
inc(d);
low[x] := d;
dfn[x] := d;
f[x] := true;
inc(deep);
stack[deep] := x;
for i := 1 to a[x,0] do
if not(v[a[x,i]]) then
begin
v[a[x,i]]:= true;
dfs(a[x,i]);
low[x] := min(low[x],low[a[x,i]]);
end
else if f[a[x,i]] then
low[x] := min(low[x],dfn[a[x,i]]);
if dfn[x]=low[x] then
inc(ans);
while stack[deep+1]<>x do
begin
f[stack[deep]] := false;
dec(deep);
end;
end;
begin
d := 0;
fillchar(a,sizeof(a),0);
for i := 1 to n do
begin
while x <> 0 do
begin
inc(rudu[x]);
inc(a[i,0]);
a[i,a[i,0]] := x;
end;
end;
for i := 1 to n do
low[i] := i;
for i := 1 to n do
if not(v[i]) then
begin
v[i] := true;
dfs(i);
end;
writeln(ans);
end.

• @ 2016-10-22 22:38:21

和2一样的啊。。。水水的并查集ac

• @ 2016-10-09 17:36:29

编译成功

foo.cpp: In function 'void cal()':
foo.cpp:55:6: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
int flag=0;
^

测试数据 #0: Accepted, time = 0 ms, mem = 59288 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 59284 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 59288 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 59284 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 59284 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 59284 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 59284 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 59280 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 59284 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 59288 KiB, score = 10

Accepted, time = 45 ms, mem = 59288 KiB, score = 100

代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int const MAXN=1000000;
int vis[MAXN],mark[MAXN],ss[MAXN],cnt,in[MAXN],Tree[MAXN];
struct EDGE{
int next,to,val;
}edge1[MAXN],edge2[MAXN];
edge1[num_edge1].to=to;
}
edge2[num_edge2].to=to;
}
void DFS1(int s){
mark[s]=1;
int v=edge1[i].to;
if(!mark[v]){
DFS1(v);
}
}
ss[++ss[0]]=s;

}
void DFS2(int s){
num[s]=cnt;
++tree_n[cnt];
mark[s]=1;
int v=edge2[i].to;
if(!mark[v]){
DFS2(v);
}
}
}
void cal(){
memset(mark,0,sizeof(mark));
for (int i=1;i<=n;i++){
int v=edge1[j].to;
if(num[i]!=num[v])
mark[num[i]]=1;
}
}
int flag=0;
for (int i=1;i<=cnt;i++){
if(!mark[i]){
flag=i;ans++;
}
}
//if(ans==1) cout<<tree_n[flag];
//else cout<<'0'
cout<<ans;
}
int main(){
//freopen("kos.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++){int a;
while(scanf("%d",&a)&&a){
}
}
for (int i=1;i<=n;i++){
if(!mark[i])
DFS1(i);
}
memset(mark,0,sizeof(mark));
for (int i=ss[0];i>0;i--){
if(!mark[ss[i]]) {
cnt++;
DFS2(ss[i]);
}
}
cal();
return 0;
}

• @ 2016-08-20 10:55:40

真心感觉数据是错的2333
并查集解法的反例：

3
2 0
0
2 0

实际答案应为2，但并查集输出1
所以我写了一个卡时搜索，结果0
RP-------

• @ 2016-08-13 09:37:37

var p:array[1..1000,1..1000]of boolean;
dfn,low,f:array[1..1000]of longint;
s,ss:array[1..1000]of boolean;
n,i,b,h,t,ans:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
procedure tarjan(x:longint);
var i,j,k:longint;
begin
inc(h);
dfn[x]:=h;low[x]:=h;
inc(t); f[t]:=x;
s[x]:=true;ss[x]:=true;
for i:=1 to 200 do
if p[x,i] then
begin
if not s[i] then
begin
tarjan(i);
low[x]:=min(low[x],low[i]);
end
else if ss[i] then low[x]:=min(low[x],dfn[i]);
end;
if dfn[x]=low[x] then
begin
inc(ans);
while f[t+1]<>x do
begin
ss[f[t]]:=false;
dec(t);
end;
end;
end;
begin
for i:=1 to n do
begin
while true do
begin
if b=0 then break;
p[b,i]:=true;p[i,b]:=true;
end;
end;
for i:=1 to n do low[i]:=i;
for i:=1 to n do
if not s[i] then tarjan(i);
writeln(ans);
end.

• @ 2016-08-01 19:53:28
program vijos1023;
var
ans,b,c,t,n,i,j,k,l:longint;
a,a2,a3:array[0..1000,0..2] of longint;
o2,o3,zhan,kind,o,low,dfn:array[0..1000] of longint;
top,cc,now,tot,pop,tot2,tot3:longint;
f,inz:array[0..1000] of boolean;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
inc(tot2);
a2[tot2,1]:=q;
a2[tot2,0]:=o2[p];
o2[p]:=tot2;
end;
begin
inc(tot3);
f[q]:=false;
a3[tot3,1]:=q;
a3[tot3,0]:=o3[p];
o3[p]:=tot3;
end;
begin
inc(tot);
a[tot,1]:=q;
a[tot,0]:=o[p];
o[p]:=tot;
end;
procedure init;
begin
tot:=0;
tot2:=0;
tot3:=0;
ans:=0;
cc:=0;
pop:=0;
top:=0;
fillchar(inz,sizeof(inz),false);
fillchar(f,sizeof(f),true);
fillchar(dfn,sizeof(dfn),0);
for i:=1 to n do
begin
while true do
begin
if b=0 then break;
end;
end;
end;
procedure dfs(x:longint);
var
t,now:longint;
begin
inc(cc);
low[x]:=cc;
dfn[x]:=cc;
inc(top);
zhan[top]:=x;
inz[x]:=true;
t:=o[x];
while (t<>0) do
begin
if (dfn[a[t,1]]=0)then
begin
dfs(a[t,1]);
low[x]:=min(low[x],low[a[t,1]]);
end
else
if inz[a[t,1]] then
low[x]:=min(low[x],low[a[t,1]]);
t:=a[t,0];
end;
if (dfn[x]=low[x]) then
begin
inc(pop);
while (zhan[top]<>x) do
begin
now:=zhan[top];
kind[now]:=pop;
inz[zhan[top]]:=false;
dec(top);
end;
now:=zhan[top];
inz[zhan[top]]:=false;
top:=top-1;
kind[now]:=pop;
end;
end;
procedure tarjan;
var
i,t:longint;
begin
for i:=1 to  n do
begin
if (dfn[i]=0) then dfs(i);
end;
for i:=1 to n do
begin
t:=o[i];
while t<>0 do
begin
if (kind[i]<>kind[a[t,1]])   then
begin
end;
t:=a[t,0];
end;
end;
end;
procedure serch;
begin
for i:=1 to pop do
begin
if f[i] then inc(ans);
end;
writeln(anns);
end;
begin
init;
tarjan;
serch;
end.

ID
1023

4

4310

1967

46%

12