Pagini recente » Cod sursa (job #2459439) | Cod sursa (job #699154) | Cod sursa (job #78300) | Cod sursa (job #366094) | Cod sursa (job #545995)
Cod sursa(job #545995)
#include<fstream>
#include<vector>
#include<stack>
#define dmax 100010
#define inf 999999
using namespace std;
int n,m;
vector <int> a[dmax],ctc[dmax];
stack <int> s;
int index[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;
index[nod] = lowlink[nod] = ind;
ind++;
s.push(nod); ins[nod] = 1;
for (i=0; i<(int)a[nod].size(); i++)
if (index[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], index[a[nod][i]]);
if (index[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++)
index[i] = lowlink[i] = inf;
for (i=1; i<=n; i++)
if (index[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;
}