DSU-O(n^2)
\nstruct unionfind\n{\n    int n;\n    // vector<int> rank;\n    vector<int> parent;\n    unionfind(int n)\n    {\n        \n        // fill(rank.begin(), rank.
```\nstruct unionfind\n{\n    int n;\n    // vector<int> rank;\n    vector<int> parent;\n    unionfind(int n)\n    {\n        \n        // fill(rank.begin(), rank.end(), 0);\n        parent.resize(n);\n        for (int i = 0; i < n; i++)\n        {\n            parent[i] = i;\n        }\n    }\n    int find(int node)\n    {\n        if (node == parent[node])\n        {\n            return node;\n        }\n        else\n        {\n            return parent[node] = find(parent[node]);\n        }\n    }\n    bool Union(int u, int v)\n    {\n        u = find(u);\n        v = find(v);\n        if (u == v)\n        {\n            return false;\n        }\n        \n        parent[v] = u;\n        return true;\n    }\n};\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& v) {\n        int n=v.size();\n        unionfind u = unionfind(n);\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(v[i][j]){\n                    u.Union(i,j);\n                }\n            }\n        }\n        int dp[n][n];\n        memset(dp,0,sizeof(dp));\n        for(int i=n-1;i>=0;i--){\n            for(int j=n-1;j>=0;j--){\n                if(u.find(i)==u.find(j)){\n                    dp[i][j]=1;\n                    if(i+1<n && j+1<n){\n                        dp[i][j] = dp[i+1][j+1]+1;\n                    }\n                }\n                if(dp[i][j]!=v[i][j]){\n                    return "";\n                }\n            }\n        }\n        // cout<<1;\n        char x = \'a\'-1;\n        string s="";\n        map<char,int>m;\n        for(int i=0;i<n;i++){\n            if(m.find(u.find(i))!=m.end()){\n                s+=m[u.find(i)];\n            }\n            else{\n                x++;\n                m[u.find(i)]=x;\n                s+=x;\n            }\n        }\n        if(x>\'z\'){\n            return "";\n        }\n        return s;\n    }\n};\n```
['Graph']