题目:hdu 1181 变形果
题意:给一些边,求传递闭包中B->M是否为真。
题解:第一个传递闭包,很裸。
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back typedef long long ll; const int maxint = 0x7fffffff; const ll maxll = 1LL<<60; int g[30][30]; string s; int main(){ #ifndef in ios::sync_with_stdio(false); #endif int from, to; while(cin >> s){ memset(g, 0, sizeof(g)); if( s == "0" ) break; from = s[0] - 'a'; to = s[s.length()-1] - 'a'; g[from][to] = 1; while(cin >> s){ if( s == "0" ) break; from = s[0] - 'a'; to = s[s.length()-1] - 'a'; g[from][to] = 1; } for(int k = 0; k < 26; k ++){ for(int i = 0; i < 26; i ++){ for(int j = 0; j < 26; j ++){ g[i][j] = g[i][j] | (g[i][k]&g[k][j]); } } } from = 'b' - 'a'; to = 'm' - 'a'; if( g[from][to] ) cout << "Yes." << endl; else cout << "No." << endl; } return 0; }