Untitled
unknown
plain_text
2 years ago
2.0 kB
3
Indexable
#include<iostream> using namespace std; int N; int soLangCoLap; int cau; int vung; int arrLang[301][301]; int front, rear; int visitedLang[301]; int Q[10000]; int checkTruChinh; int visited[301]; int cntVung; int cntCau; void dfs(int root, int parent, int lang, int cnt) { visited[lang] = 1; for (int i = 0; i < N; i++) { if (arrLang[lang][i] == 1 && visited[i] == 0) { dfs(root, lang, i, cnt+1); } if (arrLang[lang][i] == 1 && visited[i] == 1 && i == root && i != parent && cnt > 1) { checkTruChinh = true; break; } } visited[lang] = 0; if(checkTruChinh) for (int i = 0; i < N; i++) { if (lang != root) { if (arrLang[lang][i] == 1 && visited[i] == 0) { arrLang[parent][i] = 1; arrLang[i][parent] = 1; } arrLang[lang][i] = 0; arrLang[i][lang] = 0; } } } void bfs(int lang){ front = rear = 0; Q[rear++] = lang; visitedLang[lang] = 1; int check = false; while (front != rear) { int l = Q[front++]; for (int i = 0; i < N; i++) { if (arrLang[l][i] == 1 && visitedLang[i] == 0) { if (!check) { cntVung++; check = true; } Q[rear++] = i; visitedLang[i] = 1; } } } cntCau += (rear - 1); } int main() { freopen("input.txt", "r", stdin); int T; int temp = 0; cin >> T; for (int tc = 1; tc <= T ; tc++) { soLangCoLap = 0; cau = 0; vung = 0; cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> arrLang[i][j]; } visitedLang[i] = 0; visited[i] = 0; } for (int i = 0; i < N; i++) { temp = 0; for (int j = 0; j < N; j++) { if (arrLang[i][j] == 1) { temp++; } } if (temp == 0) { soLangCoLap++; } } cntVung = 0; for (int i = 0; i < N; i++) { bfs(i); } vung = cntVung; for (int i = 0; i < N; i++) { checkTruChinh = false; dfs(i, i, i, 1); } for (int i = 0; i < N; i++) { visitedLang[i] = 0; } cntCau = 0; for (int i = 0; i < N; i++) { bfs(i); } cau = cntCau; cout << vung+soLangCoLap << " " << soLangCoLap << " " << cau << endl; } return 0; }
Editor is loading...