PKU2019数据结构与算法实习作业 11~21

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
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 nxt[200005][26];
int fail[200005],danger[200005],q[200005];
char ch[200005];
struct acm
{
	int cnt;	
	acm(){
		cnt=1;
		for(int i=0;i<26;i++)nxt[0][i]=1;
	}
	void insert(){
		scanf("%s",ch);
		int now=1,l=strlen(ch);
		for(int i=0;i<l;i++)
		{
            int y=ch[i]-'a';
			if(!nxt[now][y])nxt[now][y]=++cnt;
			now=nxt[now][y];
		}
		danger[now]=1;
	}
    bool find(){
        scanf("%s",ch);
		int now=1,l=strlen(ch);
        for(int i=0;i<l;i++)
        {
            int y=ch[i]-'a';
            while(!nxt[now][y])
                now=fail[now];
            now=nxt[now][y];
            if(danger[now])return 1;
        }
        return 0;
    }
	void buildfail(){
		int head=0,tail=1;
		q[0]=1;fail[0]=1;
		while(head!=tail)
		{
			int now=q[head];head++;
			for(int i=0;i<26;i++)
			{
				int v=nxt[now][i];
				if(!v)continue;
				int k=fail[now];
				while(!nxt[k][i])k=fail[k];
				fail[v]=nxt[k][i];
				danger[v]|=danger[nxt[k][i]];
				q[tail++]=v;
			}
		}
	}
}acm;
int n, m;
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
        acm.insert();
    acm.buildfail();
    m = read();
    for(int i = 1; i <= m; i++)
        if(acm.find())
            puts("YES");
        else
            puts("NO");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

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 nxt[200005][26];

int fail[200005],danger[200005],q[200005];

char ch[200005];

struct acm

{

int cnt;

acm(){

cnt=1;

for(int i=0;i<26;i++)nxt[0][i]=1;

}

void insert(){

scanf("%s",ch);

int now=1,l=strlen(ch);

for(int i=0;i<l;i++)

{

int y=ch[i]-'a';

if(!nxt[now][y])nxt[now][y]=++cnt;

now=nxt[now][y];

}

danger[now]=1;

}

bool find(){

scanf("%s",ch);

int now=1,l=strlen(ch);

for(int i=0;i<l;i++)

{

int y=ch[i]-'a';

while(!nxt[now][y])

now=fail[now];

now=nxt[now][y];

if(danger[now])return 1;

}

return 0;

}

void buildfail(){

int head=0,tail=1;

q[0]=1;fail[0]=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=0;i<26;i++)

{

int v=nxt[now][i];

if(!v)continue;

int k=fail[now];

while(!nxt[k][i])k=fail[k];

fail[v]=nxt[k][i];

danger[v]|=danger[nxt[k][i]];

q[tail++]=v;

}

}acm;

int n, m;

int main()

{

n = read();

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

acm.insert();

acm.buildfail();

m = read();

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

if(acm.find())

puts("YES");

else

puts("NO");

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000007
#define inf 1000000000
#define dfsnx(x,y,d) y==4?dfs(x+1,1,d):dfs(x,y+1,d)
using namespace std;
ll read()
{
    int 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,T,cnt,ans;
char a[1005],c[5500005],b[5500005];
int ch[250005][26];
int fa[250005],val[250005];
int q[250005];
void insert()
{
     int p=strlen(a+1);
     int now=1;
     for(int i=1;i<=p;i++)
     {
         if(!ch[now][a[i]-'A'])
             ch[now][a[i]-'A']=++cnt;
         now=ch[now][a[i]-'A'];
     }
     val[now]++;
}
void bfs()
{
     int head=0,tail=1;
     q[0]=1;
     while(head!=tail)
     {
         int now=q[head];head++;
         for(int i=0;i<26;i++)
             if(ch[now][i])
             {
                 int y=ch[now][i];
                 int t=fa[now];
                 while(!ch[t][i])t=fa[t];
                 fa[y]=ch[t][i];
                 q[tail++]=y;
             }
     }
}
void get(int x)
{
    if(val[x]==-1||x==0)return;
    ans+=val[x];val[x]=-1;get(fa[x]);
 }
void query()
{
     int now=1;
     for(int i=1;i<=m;i++)
     {
         while(!ch[now][b[i]-'A'])now=fa[now];
         now=ch[now][b[i]-'A'];
         get(now);
     }
}
void pre()
{
    m=0;
    int l=strlen(c+1);
    for(int i=1,j;i<=l;i++)
        if(c[i]=='[')
        {
            int tmp=0;
            j=i+1;
            while(c[j]>='0'&&c[j]<='9')
                tmp=tmp*10+c[j]-'0',j++;
            while(tmp--)
                b[++m]=c[j];
            i=j+1;
        }
        else b[++m]=c[i];
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();
        cnt=1;ans=0;
        memset(val,0,sizeof(val));
        memset(fa,0,sizeof(fa));
        
        for(int j=0;j<26;j++)
            ch[0][j]=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",a+1);
            insert();
        }
        bfs();
        scanf("%s",c+1);
        pre();
        query();
        for(int i=1;i<=m/2;i++)
            swap(b[i],b[m-i+1]);
        query();
        for(int i=1;i<=cnt;i++)
            for(int j=0;j<26;j++)
                ch[i][j]=0;

        cout<<ans<<endl;
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include<map>

#include<set>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000007

#define inf 1000000000

#define dfsnx(x,y,d) y==4?dfs(x+1,1,d):dfs(x,y+1,d)

using namespace std;

ll read()

{

int 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,T,cnt,ans;

char a[1005],c[5500005],b[5500005];

int ch[250005][26];

int fa[250005],val[250005];

int q[250005];

void insert()

{

int p=strlen(a+1);

int now=1;

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

{

if(!ch[now][a[i]-'A'])

ch[now][a[i]-'A']=++cnt;

now=ch[now][a[i]-'A'];

}

val[now]++;

}

void bfs()

{

int head=0,tail=1;

q[0]=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=0;i<26;i++)

if(ch[now][i])

{

int y=ch[now][i];

int t=fa[now];

while(!ch[t][i])t=fa[t];

fa[y]=ch[t][i];

q[tail++]=y;

}

void get(int x)

{

if(val[x]==-1||x==0)return;

ans+=val[x];val[x]=-1;get(fa[x]);

}

void query()

{

int now=1;

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

{

while(!ch[now][b[i]-'A'])now=fa[now];

now=ch[now][b[i]-'A'];

get(now);

}

void pre()

{

m=0;

int l=strlen(c+1);

for(int i=1,j;i<=l;i++)

if(c[i]=='[')

{

int tmp=0;

j=i+1;

while(c[j]>='0'&&c[j]<='9')

tmp=tmp*10+c[j]-'0',j++;

while(tmp--)

b[++m]=c[j];

i=j+1;

}

else b[++m]=c[i];

}

int main()

{

T=read();

while(T--)

{

n=read();

cnt=1;ans=0;

memset(val,0,sizeof(val));

memset(fa,0,sizeof(fa));

for(int j=0;j<26;j++)

ch[0][j]=1;

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

{

scanf("%s",a+1);

insert();

}

bfs();

scanf("%s",c+1);

pre();

query();

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

swap(b[i],b[m-i+1]);

query();

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

for(int j=0;j<26;j++)

ch[i][j]=0;

cout<<ans<<endl;

}

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n;
struct acm
{
	int cnt;
	int next[30005][2];
	int fail[30005],danger[30005],q[30005];
	bool vis[30005],ins[30005];
	char ch[30005];
	acm(){
		cnt=1;
		for(int i=0;i<2;i++)next[0][i]=1;
	}
	void insert(){
		scanf("%s",ch);
		int now=1,l=strlen(ch);
		for(int i=0;i<l;i++)
		{
			if(!next[now][ch[i]-'0'])next[now][ch[i]-'0']=++cnt;
			now=next[now][ch[i]-'0'];
		}
		danger[now]=1;
	}
	void buildfail(){
		int head=0,tail=1;
		q[0]=1;fail[0]=1;
		while(head!=tail)
		{
			int now=q[head];head++;
			for(int i=0;i<2;i++)
			{
				int v=next[now][i];
				if(!v)
					continue;
				int k=fail[now];
				while(!next[k][i])k=fail[k];
				fail[v]=next[k][i];
				danger[v]|=danger[next[k][i]];
				q[tail++]=v;
			}
		}
	}
    bool dfs(int x){
		ins[x]=1;
	    for(int i=0;i<2;i++)
		{
			int v=next[x][i];
			if(ins[v])return 1;
			if(vis[v]||danger[v])continue;
			vis[v]=1;
			if(dfs(v))return 1;
		}
		ins[x]=0;
		return 0;
	}
}acm;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		acm.insert();
	acm.buildfail();
	if(acm.dfs(1))puts("TAK");
	else puts("NIE");
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int n;

struct acm

{

int cnt;

int next[30005][2];

int fail[30005],danger[30005],q[30005];

bool vis[30005],ins[30005];

char ch[30005];

acm(){

cnt=1;

for(int i=0;i<2;i++)next[0][i]=1;

}

void insert(){

scanf("%s",ch);

int now=1,l=strlen(ch);

for(int i=0;i<l;i++)

{

if(!next[now][ch[i]-'0'])next[now][ch[i]-'0']=++cnt;

now=next[now][ch[i]-'0'];

}

danger[now]=1;

}

void buildfail(){

int head=0,tail=1;

q[0]=1;fail[0]=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=0;i<2;i++)

{

int v=next[now][i];

if(!v)

continue;

int k=fail[now];

while(!next[k][i])k=fail[k];

fail[v]=next[k][i];

danger[v]|=danger[next[k][i]];

q[tail++]=v;

}

bool dfs(int x){

ins[x]=1;

for(int i=0;i<2;i++)

{

int v=next[x][i];

if(ins[v])return 1;

if(vis[v]||danger[v])continue;

vis[v]=1;

if(dfs(v))return 1;

}

ins[x]=0;

return 0;

}

}acm;

int main()

{

scanf("%d",&n);

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

acm.insert();

acm.buildfail();

if(acm.dfs(1))puts("TAK");

else puts("NIE");

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
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 nxt[1005][4];
int fail[1005],danger[1005],q[1005];
char ch[1005];
int f[1005][1005];
map<char, int>mp;
struct acm
{
	int cnt;	
	acm(){
        clear();
	}
    void clear(){
        cnt=1;
        memset(nxt, 0, sizeof(nxt));
		for(int i=0;i<4;i++)nxt[0][i]=1;
        memset(danger, 0, sizeof(danger));
        memset(fail, 0, sizeof(fail));
    }
	void insert(){
		scanf("%s",ch);
		int now=1,l=strlen(ch);
		for(int i=0;i<l;i++)
		{
            int y=mp[ch[i]];
			if(!nxt[now][y])nxt[now][y]=++cnt;
			now=nxt[now][y];
		}
		danger[now]=1;
	}
	void buildfail(){
		int head=0,tail=1;
		q[0]=1;fail[0]=1;
		while(head!=tail)
		{
			int now=q[head];head++;
			for(int i=0;i<4;i++)
			{
				int v=nxt[now][i];
				if(!v)continue;
				int k=fail[now];
				while(!nxt[k][i])k=fail[k];
				fail[v]=nxt[k][i];
				danger[v]|=danger[nxt[k][i]];
				q[tail++]=v;
			}
		}
	}
    int dp(){
        scanf("%s", ch);
		int now = 1,l = strlen(ch);
        memset(f, 127/3, sizeof(f));
        f[1][0] = 0;        
        for(int i = 0; i < l; i++)
		{
            int y=mp[ch[i]];
            for(int j = 1; j <= cnt; j++)
            {
                if(danger[j])continue;
                for(int k = 0; k < 4; k++)
                {
                    int now = j;
                    while(!nxt[now][k])now = fail[now];
                    now = nxt[now][k];
                    if(danger[now])continue;
                    f[now][i + 1] = min(f[now][i + 1], f[j][i] + (k != y));
                }
            }
        }
        int ans = inf;
        for(int i = 1; i <= cnt; i++)
            ans = min(ans, f[i][l]);
        if(ans > l)return -1;
        return ans;
    }
}acm;
int n, m;
int main()
{
    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['T'] = 3;
    int T = 0;
    while(1)
    {
        n = read();
        T++;
        if(n == 0)break;
        acm.clear();        
        printf("Case %d: ", T);
        for(int i = 1; i <= n; i++)
            acm.insert();
        acm.buildfail();
        int ans = acm.dp();
        cout << ans << endl;
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

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 nxt[1005][4];

int fail[1005],danger[1005],q[1005];

char ch[1005];

int f[1005][1005];

map<char, int>mp;

struct acm

{

int cnt;

acm(){

clear();

}

void clear(){

cnt=1;

memset(nxt, 0, sizeof(nxt));

for(int i=0;i<4;i++)nxt[0][i]=1;

memset(danger, 0, sizeof(danger));

memset(fail, 0, sizeof(fail));

}

void insert(){

scanf("%s",ch);

int now=1,l=strlen(ch);

for(int i=0;i<l;i++)

{

int y=mp[ch[i]];

if(!nxt[now][y])nxt[now][y]=++cnt;

now=nxt[now][y];

}

danger[now]=1;

}

void buildfail(){

int head=0,tail=1;

q[0]=1;fail[0]=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=0;i<4;i++)

{

int v=nxt[now][i];

if(!v)continue;

int k=fail[now];

while(!nxt[k][i])k=fail[k];

fail[v]=nxt[k][i];

danger[v]|=danger[nxt[k][i]];

q[tail++]=v;

}

int dp(){

scanf("%s", ch);

int now = 1,l = strlen(ch);

memset(f, 127/3, sizeof(f));

f[1][0] = 0;

for(int i = 0; i < l; i++)

{

int y=mp[ch[i]];

for(int j = 1; j <= cnt; j++)

{

if(danger[j])continue;

for(int k = 0; k < 4; k++)

{

int now = j;

while(!nxt[now][k])now = fail[now];

now = nxt[now][k];

if(danger[now])continue;

f[now][i + 1] = min(f[now][i + 1], f[j][i] + (k != y));

}

int ans = inf;

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

ans = min(ans, f[i][l]);

if(ans > l)return -1;

return ans;

}

}acm;

int n, m;

int main()

{

mp['A'] = 0;

mp['C'] = 1;

mp['G'] = 2;

mp['T'] = 3;

int T = 0;

while(1)

{

n = read();

T++;

if(n == 0)break;

acm.clear();

printf("Case %d: ", T);

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

acm.insert();

acm.buildfail();

int ans = acm.dp();

cout << ans << endl;

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
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, K;
int height[1000005], Rank[1000005], s[1000005], pos[1000005];
char ans[205];
int wa[1000005], wb[1000005], wv[1000005], Ws[1000005];
int sa[1000005];
bool vis[4005];
void BuildSA() {
    int i, j, p, *pm = wa, *k2sa = wb, *t;
    for (i = 0; i<m; i++) Ws[i] = 0;
    for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;
    for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {
        for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;
        for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;
        for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];
        for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];
            if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])
                pm[sa[i]] = p - 1;
            else
                pm[sa[i]] = p++;
        }
    }
    return;
}
void BuildHeight() {    
    int i, j, k;
    for(int i = 0; i < n; ++i)
        Rank[sa[i]] =  i;
    height[0] = 0;
    for (i = k = 0; i < n - 1; height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1];
                  s[i+k]==s[j+k]; k++);
}
bool check(int mid)
{
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for(int i = 1; i < n; i++)
    {
        if(height[i] < mid)
        {
            memset(vis, 0, sizeof(vis));
            cnt = 0;
            continue;
        }
        if(!vis[pos[sa[i]]])vis[pos[sa[i]]] = 1, cnt++;
        if(!vis[pos[sa[i - 1]]])vis[pos[sa[i - 1]]] = 1, cnt++;
        if(cnt == K)
        {
            for(int j = 0; j < mid; j++)
                ans[j] = s[sa[i] + j] + 'a' - 1;
            return 1;
        }
    }
    return 0;
}
int main()
{
    while(1)
    {
        K = read();
        if(!K)break;
        n = 0; m = 27;
        char str[205];
        for(int i = 1; i <= K; i++)
        {
            scanf("%s", str);
            int l = strlen(str);
            for(int j = 0; j < l; j++)
            {
                pos[n] = i;
                s[n++] = str[j] - 'a' + 1;
            }
            pos[n] = i;
            s[n++] = m++;
        }
        s[n++] = 0;
        BuildSA();
        BuildHeight();
        int l = 0, r = 200, ansl = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid))ansl = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(!ansl)
            puts("IDENTITY LOST");
        else
        {
            for(int i = 0; i < ansl; i++)
                printf("%c", ans[i]);
            cout << endl;
        }
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

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, K;

int height[1000005], Rank[1000005], s[1000005], pos[1000005];

char ans[205];

int wa[1000005], wb[1000005], wv[1000005], Ws[1000005];

int sa[1000005];

bool vis[4005];

void BuildSA() {

int i, j, p, *pm = wa, *k2sa = wb, *t;

for (i = 0; i<m; i++) Ws[i] = 0;

for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;

for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {

for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;

for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;

for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;

for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];

for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];

if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])

pm[sa[i]] = p - 1;

else

pm[sa[i]] = p++;

}

return;

}

void BuildHeight() {

int i, j, k;

for(int i = 0; i < n; ++i)

Rank[sa[i]] = i;

height[0] = 0;

for (i = k = 0; i < n - 1; height[Rank[i++]] = k)

for (k ? k-- : 0, j = sa[Rank[i] - 1];

s[i+k]==s[j+k]; k++);

}

bool check(int mid)

{

memset(vis, 0, sizeof(vis));

int cnt = 0;

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

{

if(height[i] < mid)

{

memset(vis, 0, sizeof(vis));

cnt = 0;

continue;

}

if(!vis[pos[sa[i]]])vis[pos[sa[i]]] = 1, cnt++;

if(!vis[pos[sa[i - 1]]])vis[pos[sa[i - 1]]] = 1, cnt++;

if(cnt == K)

{

for(int j = 0; j < mid; j++)

ans[j] = s[sa[i] + j] + 'a' - 1;

return 1;

}

return 0;

}

int main()

{

while(1)

{

K = read();

if(!K)break;

n = 0; m = 27;

char str[205];

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

{

scanf("%s", str);

int l = strlen(str);

for(int j = 0; j < l; j++)

{

pos[n] = i;

s[n++] = str[j] - 'a' + 1;

}

pos[n] = i;

s[n++] = m++;

}

s[n++] = 0;

BuildSA();

BuildHeight();

int l = 0, r = 200, ansl = 0;

while(l <= r)

{

int mid = (l + r) >> 1;

if(check(mid))ansl = mid, l = mid + 1;

else r = mid - 1;

}

if(!ansl)

puts("IDENTITY LOST");

else

{

for(int i = 0; i < ansl; i++)

printf("%c", ans[i]);

cout << endl;

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 200005
using namespace std;
char ch[N];
int n;
int a[N],v[N],h[N],sa[2][N],rk[2][N];
int p,q,k;
void calsa(int *sa,int *rk,int *SA,int *RK)
{
	for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;
	for(int i=n;i;i--)
		if(sa[i]>k)
			SA[v[rk[sa[i]-k]]--]=sa[i]-k;
	for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
	for(int i=1;i<=n;i++)
		RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
}
void getsa()
{
	p=0,q=1,k=1;
	for(int i=1;i<=n;i++)v[a[i]]++;
	for(int i=1;i<=30;i++)v[i]+=v[i-1];
	for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;
	for(int i=1;i<=n;i++)
		rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
	for(k=1;k<n;k<<=1,swap(p,q))
		calsa(sa[p],rk[p],sa[q],rk[q]);
}
void geth()
{
	k=0;
	for(int i=1;i<=n;i++)
		if(rk[p][i]==1)h[rk[p][i]]=0;
		else
		{
			int j=sa[p][rk[p][i]-1];
			while(a[i+k]==a[j+k])k++;
			h[rk[p][i]]=k;
			if(k>0)k--;
		}
}
int main()
{
	scanf("%s",ch+1);
	int l=strlen(ch+1);
	ch[++l]='z'+1;
	scanf("%s",ch+l+1);
	n=strlen(ch+1);
	for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;
	getsa();
	geth();
	int ans=0;
	for(int i=2;i<=n;i++)
		if(sa[p][i]<l&&sa[p][i-1]>l)
			ans=max(h[i],ans);
		else if(sa[p][i]>l&&sa[p][i-1]<l)
			ans=max(h[i],ans);
	printf("%d",ans);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define ll long long

#define N 200005

using namespace std;

char ch[N];

int n;

int a[N],v[N],h[N],sa[2][N],rk[2][N];

int p,q,k;

void calsa(int *sa,int *rk,int *SA,int *RK)

{

for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;

for(int i=n;i;i--)

if(sa[i]>k)

SA[v[rk[sa[i]-k]]--]=sa[i]-k;

for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;

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

RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);

}

void getsa()

{

p=0,q=1,k=1;

for(int i=1;i<=n;i++)v[a[i]]++;

for(int i=1;i<=30;i++)v[i]+=v[i-1];

for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;

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

rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);

for(k=1;k<n;k<<=1,swap(p,q))

calsa(sa[p],rk[p],sa[q],rk[q]);

}

void geth()

{

k=0;

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

if(rk[p][i]==1)h[rk[p][i]]=0;

else

{

int j=sa[p][rk[p][i]-1];

while(a[i+k]==a[j+k])k++;

h[rk[p][i]]=k;

if(k>0)k--;

}

int main()

{

scanf("%s",ch+1);

int l=strlen(ch+1);

ch[++l]='z'+1;

scanf("%s",ch+l+1);

n=strlen(ch+1);

for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;

getsa();

geth();

int ans=0;

for(int i=2;i<=n;i++)

if(sa[p][i]<l&&sa[p][i-1]>l)

ans=max(h[i],ans);

else if(sa[p][i]>l&&sa[p][i-1]<l)

ans=max(h[i],ans);

printf("%d",ans);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
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;
}
ll ans;
int n, m, K, top, l1, l2;
int height[200005], Rank[200005], s[200005];
char str[200005];
int wa[200005], wb[200005], wv[200005], Ws[200005], sa[200005];
ll num[200005], h[200005], w[200005];
void BuildSA() {
    int i, j, p, *pm = wa, *k2sa = wb, *t;
    for (i = 0; i<m; i++) Ws[i] = 0;
    for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;
    for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {
        for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;
        for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;
        for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];
        for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];
            if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])
                pm[sa[i]] = p - 1;
            else
                pm[sa[i]] = p++;
        }
    }
    return;
}
void BuildHeight() {    
    int i, j, k;
    for(int i = 0; i < n; ++i)
        Rank[sa[i]] =  i;
    height[0] = 0;
    for (i = k = 0; i < n - 1; height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1];
                  s[i+k]==s[j+k]; k++);
}
void solve()
{
    for(int i = 1; i < n; i++)
        height[i] = max(0, height[i] - K + 1);
    top = 0;
    for(int i = 1; i < n; i++)
        if(height[i] == 0)
            top = 0;
        else
        {
            int tmp = 0;           
            while(top && h[top] >= height[i])
                tmp += w[top], top--;
            h[++top] = height[i];
            w[top] = tmp + (sa[i - 1] > l1);
            num[top] = num[top - 1] + h[top] * w[top];
            if(sa[i] < l1)
                ans += num[top];
        }
    top = 0;
    for(int i = 1; i < n; i++)
        if(height[i] == 0)
            top = 0;
        else
        {
            int tmp = 0;            
            while(top && h[top] >= height[i])
                tmp += w[top], top--;
            h[++top] = height[i];
            w[top] = tmp + (sa[i - 1] < l1);            
            num[top] = num[top - 1] + h[top] * w[top];            
            if(sa[i] > l1)
                ans += num[top];
        }    
}
int main()
{
    while(1)
    {
        K = read();
        if(!K)break;
        ans = n = 0;
        scanf("%s", str);
        l1 = strlen(str);
        m = 'z' - 'A' + 2;
        for(int i = 0; i < l1; i++)
            s[n++] = str[i] - 'A' + 1;
        s[n++] = m++;
        scanf("%s", str);
        l2 = strlen(str);
        for(int i = 0; i < l2; i++)
            s[n++] = str[i] - 'A' + 1;
        s[n++] = 0;
        BuildSA();
        BuildHeight();
        solve();
        cout << ans << endl;
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

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;

}

ll ans;

int n, m, K, top, l1, l2;

int height[200005], Rank[200005], s[200005];

char str[200005];

int wa[200005], wb[200005], wv[200005], Ws[200005], sa[200005];

ll num[200005], h[200005], w[200005];

void BuildSA() {

int i, j, p, *pm = wa, *k2sa = wb, *t;

for (i = 0; i<m; i++) Ws[i] = 0;

for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;

for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {

for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;

for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;

for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;

for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];

for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];

if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])

pm[sa[i]] = p - 1;

else

pm[sa[i]] = p++;

}

return;

}

void BuildHeight() {

int i, j, k;

for(int i = 0; i < n; ++i)

Rank[sa[i]] = i;

height[0] = 0;

for (i = k = 0; i < n - 1; height[Rank[i++]] = k)

for (k ? k-- : 0, j = sa[Rank[i] - 1];

s[i+k]==s[j+k]; k++);

}

void solve()

{

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

height[i] = max(0, height[i] - K + 1);

top = 0;

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

if(height[i] == 0)

top = 0;

else

{

int tmp = 0;

while(top && h[top] >= height[i])

tmp += w[top], top--;

h[++top] = height[i];

w[top] = tmp + (sa[i - 1] > l1);

num[top] = num[top - 1] + h[top] * w[top];

if(sa[i] < l1)

ans += num[top];

}

top = 0;

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

if(height[i] == 0)

top = 0;

else

{

int tmp = 0;

while(top && h[top] >= height[i])

tmp += w[top], top--;

h[++top] = height[i];

w[top] = tmp + (sa[i - 1] < l1);

num[top] = num[top - 1] + h[top] * w[top];

if(sa[i] > l1)

ans += num[top];

}

int main()

{

while(1)

{

K = read();

if(!K)break;

ans = n = 0;

scanf("%s", str);

l1 = strlen(str);

m = 'z' - 'A' + 2;

for(int i = 0; i < l1; i++)

s[n++] = str[i] - 'A' + 1;

s[n++] = m++;

scanf("%s", str);

l2 = strlen(str);

for(int i = 0; i < l2; i++)

s[n++] = str[i] - 'A' + 1;

s[n++] = 0;

BuildSA();

BuildHeight();

solve();

cout << ans << endl;

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
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, ind, top, scc, ans;
int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];
int u[50005], v[50005];
vector<int> e[10005];
void tarjan(int x)
{
    dfn[x] = low[x] = ++ind;
    q[++top] = x;
    inq[x] = 1;
    for(int i = 0; i < e[x].size(); i++)
        if(!dfn[e[x][i]])
        {
            tarjan(e[x][i]);
            low[x] = min(low[x], low[e[x][i]]);
        }
        else if(inq[e[x][i]])
            low[x] = min(low[x], dfn[e[x][i]]);
    if(dfn[x] == low[x])
    {
        int now = -1; scc++;
        while(now != x)
        {
            now = q[top]; top--;
            inq[now] = 0;
            bl[now] = scc;
            size[scc]++;
        }
    }
}
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        u[i] = read(), v[i] = read();
        e[v[i]].push_back(u[i]);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);
    for(int i = 1; i <= m; i++)
        if(bl[u[i]] != bl[v[i]])
            d[bl[u[i]]]++;
    for(int i = 1; i <= scc; i++)
    {
        if(d[i] == 0)
        {
            if(ans)
            {
                ans = 0;
                break;
            }
            ans = size[i];            
        }
    }
    printf("%d\n", ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

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, ind, top, scc, ans;

int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];

int u[50005], v[50005];

vector<int> e[10005];

void tarjan(int x)

{

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

q[++top] = x;

inq[x] = 1;

for(int i = 0; i < e[x].size(); i++)

if(!dfn[e[x][i]])

{

tarjan(e[x][i]);

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

}

else if(inq[e[x][i]])

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

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

{

int now = -1; scc++;

while(now != x)

{

now = q[top]; top--;

inq[now] = 0;

bl[now] = scc;

size[scc]++;

}

int main()

{

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

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

{

u[i] = read(), v[i] = read();

e[v[i]].push_back(u[i]);

}

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

if(!dfn[i])

tarjan(i);

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

if(bl[u[i]] != bl[v[i]])

d[bl[u[i]]]++;

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

{

if(d[i] == 0)

{

if(ans)

{

ans = 0;

break;

}

ans = size[i];

}

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

return 0;

}

#include<map>
#include<cmath>
#include<stack>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
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;
int top, scc, ind;
int dfn[1005], low[1005], q[1005], inq[1005], bl[1005], size[1005], d[1005];
int u[6005], v[6005];
stack<int> st;
vector<int> e[1005], e2[1005];
void tarjan(int x)
{
    dfn[x] = low[x] = ++ind;
    q[++top] = x; inq[x] = 1;
    for(int i = 0; i < e[x].size(); i++)
        if(!dfn[e[x][i]])
        {
            tarjan(e[x][i]);
            low[x] = min(low[x], low[e[x][i]]);
        }
        else if(inq[e[x][i]])
            low[x] = min(low[x], dfn[e[x][i]]);
    if(low[x] == dfn[x])
    {
        scc++;
        int cur = -1;
        while(x != cur)
        {
            cur = q[top--];
            size[scc]++;
            bl[cur] = scc;
            inq[cur] = 0;
        }
    }
}
int main()
{
    int T = read();
    while(T--)
    {
        n = read(); m = read();
        for(int i = 1; i <= m; i++)
        {
            u[i] = read(), v[i] = read();
            e[u[i]].push_back(v[i]);
        }
        for(int i = 1; i <= n; i++)
            if(!dfn[i])
                tarjan(i);
        for(int i = 1; i <= m; i++)
        {
            int p = bl[u[i]], q = bl[v[i]];
            if(p != q)
            {
                e2[p].push_back(q);
                d[q]++;
            }
        }
        for(int i = 1; i <= scc; i++)
            if(!d[i])st.push(i);
        bool flag = 1;
        while(!st.empty())
        {            
            if(st.size() > 1)flag = 0;
            int x = st.top(); st.pop();
            for(int i = 0; i < e2[x].size(); i++)
            {
                d[e2[x][i]]--;
                if(!d[e2[x][i]])
                    st.push(e2[x][i]);
            }
        }
        if(flag)puts("Yes");
        else puts("No");
        for(int i = 1; i <= n; i++)
        {
            low[i] = dfn[i] = 0;
            e[i].clear();
            e2[i].clear();
        }
        
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

#include<map>

#include<cmath>

#include<stack>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

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;

int top, scc, ind;

int dfn[1005], low[1005], q[1005], inq[1005], bl[1005], size[1005], d[1005];

int u[6005], v[6005];

stack<int> st;

vector<int> e[1005], e2[1005];

void tarjan(int x)

{

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

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

for(int i = 0; i < e[x].size(); i++)

if(!dfn[e[x][i]])

{

tarjan(e[x][i]);

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

}

else if(inq[e[x][i]])

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

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

{

scc++;

int cur = -1;

while(x != cur)

{

cur = q[top--];

size[scc]++;

bl[cur] = scc;

inq[cur] = 0;

}

int main()

{

int T = read();

while(T--)

{

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

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

{

u[i] = read(), v[i] = read();

e[u[i]].push_back(v[i]);

}

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

if(!dfn[i])

tarjan(i);

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

{

int p = bl[u[i]], q = bl[v[i]];

if(p != q)

{

e2[p].push_back(q);

d[q]++;

}

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

if(!d[i])st.push(i);

bool flag = 1;

while(!st.empty())

{

if(st.size() > 1)flag = 0;

int x = st.top(); st.pop();

for(int i = 0; i < e2[x].size(); i++)

{

d[e2[x][i]]--;

if(!d[e2[x][i]])

st.push(e2[x][i]);

}

if(flag)puts("Yes");

else puts("No");

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

{

low[i] = dfn[i] = 0;

e[i].clear();

e2[i].clear();

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
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, s, cnt;
double V, dis[105];
int q[105], last[105];
bool inq[105];
struct data{
    int to, next;
    double r, c;
}e[205];
void insert(int u, int v, double r, double c)
{
    e[++cnt] = (data){v, last[u], r, c}; last[u] = cnt;
}
bool spfa()
{   
    int head = 0, tail = 1;
    dis[s] = V; q[0] = s; inq[s] = 1;
    while(head != tail)
    {
        int x = q[head]; head++; if(head == 100)head = 0;
        for(int i = last[x]; i; i = e[i].next)
            if((dis[x] - e[i].c) * e[i].r > dis[e[i].to])
            {
                if(e[i].to == s)return 1;
                dis[e[i].to] = (dis[x] - e[i].c) * e[i].r;
                if(!inq[e[i].to])
                {
                    q[tail++] = e[i].to;
                    inq[e[i].to] = 1;
                }
                if(tail == 100)tail = 0;
            }        
        inq[x] = 0;
    }
    return 0;
}
int main()    
{
    n = read(); m = read(); s = read(); scanf("%lf", &V);
    for(int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        double R, C;
        scanf("%lf%lf", &R, &C);
        insert(u, v, R, C);
        scanf("%lf%lf", &R, &C);
        insert(v, u, R, C);
    }
    if(spfa())
        puts("YES");
    else
        puts("NO");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

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, s, cnt;

double V, dis[105];

int q[105], last[105];

bool inq[105];

struct data{

int to, next;

double r, c;

}e[205];

void insert(int u, int v, double r, double c)

{

e[++cnt] = (data){v, last[u], r, c}; last[u] = cnt;

}

bool spfa()

{

int head = 0, tail = 1;

dis[s] = V; q[0] = s; inq[s] = 1;

while(head != tail)

{

int x = q[head]; head++; if(head == 100)head = 0;

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

if((dis[x] - e[i].c) * e[i].r > dis[e[i].to])

{

if(e[i].to == s)return 1;

dis[e[i].to] = (dis[x] - e[i].c) * e[i].r;

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

{

q[tail++] = e[i].to;

inq[e[i].to] = 1;

}

if(tail == 100)tail = 0;

}

inq[x] = 0;

}

return 0;

}

int main()

{

n = read(); m = read(); s = read(); scanf("%lf", &V);

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

{

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

double R, C;

scanf("%lf%lf", &R, &C);

insert(u, v, R, C);

scanf("%lf%lf", &R, &C);

insert(v, u, R, C);

}

if(spfa())

puts("YES");

else

puts("NO");

return 0;

}

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7fffffff
#define ll long long
using namespace std;
int n, ind, tes;
int low[1005], dfn[1005], blo[1005];
vector<int> e[1005];
int tarjan(int x)
{
	low[x] = dfn[x] = ++ind;
	for(int i = 0; i < e[x].size(); i++)
		if(!dfn[e[x][i]])
		{
			tarjan(e[x][i]);
			low[x] = min(low[x], low[e[x][i]]);
			if(dfn[x] <= low[e[x][i]])
				blo[x]++;
		}
		else low[x] = min(low[x], dfn[e[x][i]]);
}
int main()
{
	int x, y;
	while(scanf("%d", &x) != EOF)
	{
		if(x == 0)break;
		n = 0;
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		scanf("%d", &y);
		n = max(n, max(x, y));
		e[x].push_back(y);
		e[y].push_back(x);
		while(scanf("%d", &x) && x)
		{			
			scanf("%d", &y);
			e[x].push_back(y);
			e[y].push_back(x);
			n = max(n, max(x, y));
		}
		for(int i = 1; i <= n; i++)blo[i] = 1; blo[1] = 0;
		tarjan(1);
		printf("Network #%d\n", ++tes);
		bool flag = 0;
		for(int i = 1; i <= n; i++)
			if(blo[i] > 1)
			{
				printf("  SPF node %d leaves %d subnets\n",i , blo[i]);
				flag = 1;
			}
		if(!flag)printf("  No SPF nodes\n");
		puts("");
		for(int i = 1; i <= n; i++)
			e[i].clear();
	}
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7fffffff

#define ll long long

using namespace std;

int n, ind, tes;

int low[1005], dfn[1005], blo[1005];

vector<int> e[1005];

int tarjan(int x)

{

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

for(int i = 0; i < e[x].size(); i++)

if(!dfn[e[x][i]])

{

tarjan(e[x][i]);

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

if(dfn[x] <= low[e[x][i]])

blo[x]++;

}

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

}

int main()

{

int x, y;

while(scanf("%d", &x) != EOF)

{

if(x == 0)break;

n = 0;

memset(dfn, 0, sizeof(dfn));

memset(low, 0, sizeof(low));

scanf("%d", &y);

n = max(n, max(x, y));

e[x].push_back(y);

e[y].push_back(x);

while(scanf("%d", &x) && x)

{

scanf("%d", &y);

e[x].push_back(y);

e[y].push_back(x);

n = max(n, max(x, y));

}

for(int i = 1; i <= n; i++)blo[i] = 1; blo[1] = 0;

tarjan(1);

printf("Network #%d\n", ++tes);

bool flag = 0;

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

if(blo[i] > 1)

{

printf(" SPF node %d leaves %d subnets\n",i , blo[i]);

flag = 1;

}

if(!flag)printf(" No SPF nodes\n");

puts("");

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

e[i].clear();

}

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论