#include <bits/stdc++.h>
using namespace std;
#define TEST
typedef unsigned int ui;
struct Path{
int length;
vector<ui> path;
Path(int length, const vector<ui> &path) : length(length), path(path) {}
bool operator<(const Path&rhs)const{
if(length!=rhs.length) return length<rhs.length;
for(int i=0;i<length;i++){
if(path[i]!=rhs.path[i])
return path[i]<rhs.path[i];
}
}
};
class Solution{
public:
vector<vector<int>> G;
unordered_map<ui,int> idHash;
vector<ui> ids;
vector<ui> inputs;
vector<int> inDegrees;
vector<bool> vis;
vector<Path> ans;
int nodeCnt;
void parseInput(string &testFile){
FILE* file=fopen(testFile.c_str(),"r");
ui u,v,c;
int cnt=0;
while(fscanf(file,"%u,%u,%u",&u,&v,&c)!=EOF){
inputs.push_back(u);
inputs.push_back(v);
++cnt;
}
#ifdef TEST
printf("%d Records in Total\n",cnt);
#endif
}
void constructGraph(){
auto tmp=inputs;
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
nodeCnt=tmp.size();
ids=tmp;
nodeCnt=0;
for(ui &x:tmp){
idHash[x]=nodeCnt++;
}
#ifdef TEST
printf("%d Nodes in Total\n",nodeCnt);
#endif
int sz=inputs.size();
G=vector<vector<int>>(nodeCnt);
inDegrees=vector<int>(nodeCnt,0);
for(int i=0;i<sz;i+=2){
int u=idHash[inputs[i]],v=idHash[inputs[i+1]];
G[u].push_back(v);
++inDegrees[v];
}
}
void dfs(int head,int cur,int depth,vector<int> &path){
vis[cur]=true;
path.push_back(cur);
for(int &v:G[cur]){
if(v==head && depth>=3 && depth<=7){
vector<ui> tmp;
for(int &x:path)
tmp.push_back(ids[x]);
ans.emplace_back(Path(depth,tmp));
}
if(depth<7 && !vis[v] && v>head){
dfs(head,v,depth+1,path);
}
}
vis[cur]=false;
path.pop_back();
}
void solve(){
vis=vector<bool>(nodeCnt,false);
vector<int> path;
for(int i=0;i<nodeCnt;i++){
if(i%100==0)
cout<<i<<"/"<<nodeCnt<<endl;
if(!G[i].empty()){
dfs(i,i,1,path);
}
}
sort(ans.begin(),ans.end());
}
void save(string &outputFile){
printf("Total Loops %d\n",(int)ans.size());
ofstream out(outputFile);
out<<ans.size()<<endl;
for(auto &x:ans){
auto path=x.path;
int sz=path.size();
out<<path[0];
for(int i=1;i<sz;i++)
out<<","<<path[i];
out<<endl;
}
}
};
int main()
{
string testFile = "test_data.txt";
string outputFile = "output.txt";
#ifdef TEST
string answerFile = "result.txt";
#endif
auto t=clock();
Solution solution;
solution.parseInput(testFile);
solution.constructGraph();
solution.solve();
solution.save(outputFile);
cout<<clock()-t<<endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)