Pagini recente » Cod sursa (job #1526671) | Cod sursa (job #2682833) | Cod sursa (job #1426950) | Cod sursa (job #889807) | Cod sursa (job #578035)
Cod sursa(job #578035)
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
bool **graf;
int N,M;
vector<int> S;
int *idx, *lowlink;
vector<vector<int> > componente;
vector<int> cmp;
void tarjan(int v)
{
static int index = -1;
int tmp;
index++;
idx[v] = lowlink[v] = index;
S.push_back(v);
for (int j=0;j<N;j++)
if (graf[v][j])
{
if (idx[j] == -1)
{
tarjan(j);
lowlink[v] = min(lowlink[j], lowlink[v]);
}
else if( find(S.begin(),S.end(),lowlink[j]) != S.end() )
lowlink[v] = min(lowlink[j], 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);
if (cmp.size()>1)
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*));
for (int i=0;i<N;i++)
{
graf[i] = (bool*)malloc(N*sizeof(bool));
idx[i] = -1;
}
for (int i=0;i<M;i++)
{
fscanf(fin,"%d%d",&start,&end);
start--;end--;
graf[start][end] = true;
}
fclose(fin);
ctc_tarjan();
FILE* fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",componente.size());
for (int i=0;i<componente.size();i++)
{
for (int j=0;j<componente[i].size();j++)
fprintf(fout,"%d ",componente[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
return 0;
}