Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
#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;
}