Pagini recente » Cod sursa (job #1452677) | Cod sursa (job #2976431) | Cod sursa (job #2847985) | Cod sursa (job #1073062) | Cod sursa (job #578078)
Cod sursa(job #578078)
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
vector<vector<int> > graf;
int N,M;
vector<int> S;
int *idx, *lowlink;
vector<vector<int> > componente;
vector<int> cmp;
int indexx = -1;
void tarjan(int v)
{
int tmp;
indexx++;
idx[v] = lowlink[v] = indexx;
S.push_back(v);
for (vector<int>::iterator it=graf[v].begin(); it<graf[v].end(); it++)
{
if (idx[*it] == -1)
{
tarjan(*it);
lowlink[v] = min(lowlink[*it], lowlink[v]);
}
else if( find(S.begin(),S.end(),lowlink[*it]) != S.end() )
lowlink[v] = min(lowlink[*it], lowlink[v]);
}
if (lowlink[v] == idx[v])
{
// este v radacina unei CTC?
//puts("O noua CTC: ");
cmp.clear();
do
{
tmp = S.back();
S.pop_back();
//printf("%d ",tmp+1);
cmp.push_back(tmp+1);
}
while (tmp != v);
componente.push_back(cmp);
//putchar('\n');
}
}
void ctc_tarjan()
{
for (int i=0;i<N;i++)
if (idx[i] == -1) // nu a fost vizitat
tarjan(i);
}
int main(int argc, char *argv[])
{
int start,end;
char filename[256] = "ctc.in";
if (argc>1)
{
strcpy(filename,argv[1]);
}
FILE* fin = fopen(filename,"r");
fscanf(fin,"%d%d",&N,&M);
idx = (int*)malloc(N*sizeof(int));
lowlink = (int*)malloc(N*sizeof(int));
//graf = (bool**)malloc(N*sizeof(bool*));
graf.resize(N);
for (int i=0;i<N;i++)
idx[i] = -1;
for (int i=0;i<M;i++)
{
fscanf(fin,"%d%d",&start,&end);
start--;end--;
graf[start].push_back(end);
}
fclose(fin);
ctc_tarjan();
FILE* fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",componente.size());
for (unsigned int i=0;i<componente.size();i++)
{
for (unsigned int j=0;j<componente[i].size();j++)
fprintf(fout,"%d ",componente[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
return 0;
}