787

Charl3s
AlbertBigcomeLu
Finn2009

kaikaihapppy

N=100010
n,m=0,0
d=[0]*N
q=[0]*N
h=[-1]*N
e=[0]*N
ne=[0]*N
idex=0
global n,m,q,h,e,ne,idex
e[idex]=b
ne[idex]=h[a]
h[a]=idex
idex+=1
def bfs():
global n,m,q,h,e,ne,idex
hh,tt=0,-1
for i in range(1,n+1):
if d[i]==0:
tt+=1
q[tt]=i
while hh<=tt:
t=q[hh]
hh+=1
i=h[t]
while i!=-1:
j=e[i]
d[j]-=1
if d[j]==0:
tt+=1
q[tt]=j
i=ne[i]
return tt==n-1
def main():
global n,m,q,h,e,ne,idex
n,m=map(int,input().split())
for i in range(m):
a,b=map(int,input().split())
d[b]+=1
if bfs():
for i in range(n):
print(q[i],end=" ")
else: print("-1")
main()

#pragma GCC optimize(2)
#include<iostream>
#include<stdio.h>
#include <cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<deque>
#include<string>
#include<unordered_set>
using namespace::std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idex = 0;
int d[N];
int n,m;
int q[N];
int bfs()
{
int hh = 0, tt = 0;
q[0] = 1;
memset(d, -1, sizeof(d));
d[1] = 0;
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] == -1)
{
d[j] = d[t] + 1;
q[++tt] = j;
}

}
}
return d[n];
}
{
e[idex] = b;
ne[idex] = h[a];
h[a] = idex++;
}
int main()
{

cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
}
cout<<bfs();
}

N=100010
M=N*2
h=[-1]*N
ne=[0]*M
e=[0]*M
idex=0
ans=N
st=[False]*N
n=0
def dfs(u):
global h,ne,idex,ans,st,n
sum,res=1,0
st[u]=True
i=h[u]
while i!=-1:
j=e[i]
if st[j]!=True:
s=dfs(j)
res=max(res,s)
sum+=s
i=ne[i]
res=max(res,n-sum)
ans=min(ans,res)
return sum
global h,ne,idex,ans,st,n
e[idex]=b
ne[idex]=h[a]
h[a]=idex
idex+=1
def main():
global h,ne,idex,ans,st,n
n=int(input())
for i in range(n-1):
a,b = map(int, input().split())
dfs(1)
print(ans)
main()

n=0
path=[[0]*7]*7
st=[0]*8
def dfs(x):
global n
if x==n:
for i in range(n):
print(path[i],end=" ")
print()
for i in range(1,4):
if st[i]==0:
st[i]=1
path[x]=i
dfs(x+1)
st[i]=0
def main():
global n
n=int(input())
dfs(0)
main()

arr=[]
q=[]
L=[-1,0,1,0]
R=[0,1,0,-1]
n,m=0,0
Distance=[[-1]*100 for i in range(100)]
def bfs():
global arr,q,L,Distance,R,n,m
Distance[0][0]=0
hh,tt=0,0
q.append((0,0))
while hh<=tt:
x,y=q[hh][0],q[hh][1]
hh+=1
for i in range(4):
tx,ty=x+L[i],y+R[i]
if tx>=0 and tx<n and ty>=0 and ty<m and arr[tx][ty]!=1and Distance[tx][ty]==-1:
Distance[tx][ty]=Distance[x][y]+1
q.append((tx,ty))
tt+=1
if tx>=0 and tx<n and ty>=0 and ty<m and tx==n-1 and ty==m-1:
return Distance[tx][ty];
break
def main():
global arr,q,L,Distance,R,n,m
n,m=map(int,input().split())
for i in range(n):
arr.append(list(map(int, input().split())))
print(bfs())
main()

# c++

#pragma GCC optimize(2)
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<deque>
#include<string>
#include<unordered_set>
using namespace::std;
int n, m;
const int K = 1e5 + 10;
int d[K];
int p[K];
//本题采用距离法确定关系，x,y距离为0为同类，x,y距离为1为x吃y
int find(int x)
{
if(p[x]!=x)
{
int t=find(p[x]);//先记录跟结点位置
d[x]+=d[p[x]];//加上之间的距离
p[x]=t;//最后赋值根节点
}
return p[x];
}
int main()
{
int n,m,sum=0;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
int t,x,y;
cin>>t>>x>>y;
int wx=find(x),wy=find(y);
if (x>n||y>n)
{
sum++;
continue;
}
if(t==1)
{
if(wx==wy&&(d[x]-d[y])%3) sum++;//x和y的距离是相等的才是同类 d[x]-d[y]=0 不等于0就是错误话
if(wx!=wy)
{
p[wx]=wy;//将wx的祖宗变成wy
d[wx]=d[y]-d[x];//d[x]+d[wx]=d[y]才是同类
}
}
else
{
if(wx==wy&&(d[x]-d[y]-1)%3)sum++; //x和y的距离是相差1才是x吃y d[x]-d[y]=1 不等于1就是错误话
if(wx!=wy)
{
p[wx]=wy;
d[wx]=d[y]-d[x]+1;//d[x]+d[wx]-d[y]=1才是x吃y
}
}
}
cout<<sum;
}

## python

K=100010
p=[0]*K
d=[0]*K
def find(x):
global p,d
if p[x]!=x:
t=find(p[x])
d[x]+=d[p[x]]
p[x]=t
return p[x]
def main():
global p,d
sum=0
n,m=map(int,input().split())
for i in range(1,n+1):
p[i]=i
while m:
m-=1
t, x, y = list(map(int, input().split()))
if x>n or y>n:
sum+=1
continue
wx,wy=find(x),find(y)
if t==1:
if wx==wy and (d[x]-d[y])%3!=0:
sum+=1
if wx!=wy:
p[wx]=wy
d[wx]=d[y]-d[x]
else:
if wx==wy and (d[x]-d[y]-1)%3!=0:
sum+=1
if wx!=wy:
p[wx]=wy
d[wx]=d[y]-d[x]+1
print(sum)
main()

N=200010
null=0x3f3f3f3f
arr=[null]*N
def find(x):
global arr,N
k=(x%N+N)%N
while arr[k]!=null and arr[k]!=x:
k+=1
if k==N:
k=0
return k
def main():
global arr
n=int(input())
for i in range(n):
p,x=input().split()
x=int(x)
k=find(x)
if p=='I':
arr[k]=x
else:
if arr[k]==x:
print("Yes")
else:
print("No")
main()

p=[0 for i in range(100010)]
shu=[0 for i in range(100010)]
def find(x):
global p,shu
if p[x]!=x:
p[x]=find(p[x])
return p[x]
def main():
global o,shu
n,m=map(int,input().split())
for i in range(1,n+1):
p[i]=i
shu[i]=1
for i in range(m):
P=input().split()
if P[0]=="C":
a,b=int(P[1]),int(P[2])
if find(a)==find(b):
continue
shu[find(b)]+=shu[find(a)]
p[find(a)]=find(b)
elif P[0]=="Q1":
a,b=int(P[1]),int(P[2])
if find(a)==find(b):
print("Yes")
else:
print("No")
else:
a=int(P[1])
print(shu[find(a)])
main()

p=[0 for i in range(100010)]
def find(x):
global p
if p[x]!=x:
p[x]=find(p[x])
return p[x]
def main():
global p
n,m=map(int,input().split())
for i in range(1,n+1):
p[i]=i
for i in range(m):
P,a,b=input().split()
a,b=int(a),int(b)
if P=='M':
p[find(a)]=find(b)
else:
if find(a)==find(b):
print("Yes")
else:
print("No")
main()

arr = [[0] * 26 for i in range(100010)]
cnt=[0]*100010
idex=0
def insert(s):
global cnt,idex,arr
p=0
for i in range(len(s)):
a=ord(s[i])-ord('a')#转换为ASCII用ord，不能像c直接用s[i]-'a'
if arr[p][a]==0:
idex+=1
arr[p][a]=idex
p=arr[p][a]
cnt[p]+=1
def inqury(s):
global cnt,idex,arr
p=0
for i in range(len(s)):
a=ord(s[i])-ord('a')
if arr[p][a]==0:
print(0)
return;
p=arr[p][a]
print(cnt[p])
def main():
global cnt,idex,arr
n=int(input())
for i in range(n):
p,s=input().split()
s=list(s)
if p=='I':
insert(s)
else:
inqury(s)
main()