Pagini recente » Borderou de evaluare (job #2474865) | Cod sursa (job #2904905) | Borderou de evaluare (job #1489341) | Borderou de evaluare (job #1355122) | Cod sursa (job #546011)
Cod sursa(job #546011)
#include<fstream>
#include<vector>
#include<stack>
#define dmax 100003
#define inf 200000
using namespace std;
int n,m;
vector <int> a[dmax],ctc[dmax];
stack <int> s;
int indeex[dmax],lowlink[dmax];
bool ins[dmax];
int ind,nrctc;
void citire()
{
int i,x,y;
ifstream fin("ctc.in");
fin>>n>>m;
for (i=1; i<=m; i++)
{
fin>>x>>y;
a[x].push_back(y);
}
fin.close();
}
void strong(int nod)
{
int i,w;
indeex[nod] = lowlink[nod] = ind;
ind++;
s.push(nod); ins[nod] = 1;
for (i=0; i<(int)a[nod].size(); i++)
if (indeex[a[nod][i]] == inf)
{
strong(a[nod][i]);
lowlink[nod] = min(lowlink[nod], lowlink[a[nod][i]]);
} else
if (ins[a[nod][i]] == 1)
lowlink[nod] = min(lowlink[nod], indeex[a[nod][i]]);
if (indeex[nod] == lowlink[nod])
{
w = s.top();
ins[s.top()] = 0; s.pop();
nrctc++;
ctc[nrctc].push_back(w);
while (w != nod)
{
w = s.top();
ins[s.top()] = 0; s.pop();
ctc[nrctc].push_back(w);
}
}
}
void tarjan()
{
int i;
for (i=1; i<=n; i++)
indeex[i] = lowlink[i] = inf;
for (i=1; i<=n; i++)
if (indeex[i] == inf)
strong(i);
}
void afisare()
{
int i,j;
ofstream fout("ctc.out");
fout<<nrctc<<'\n';
for (i=1; i<=nrctc; i++)
{
for (j=0; j<(int)ctc[i].size(); j++)
fout<<ctc[i][j]<<" ";
fout<<'\n';
}
fout.close();
}
int main()
{
citire();
tarjan();
afisare();
return 0;
}