Pagini recente » Cod sursa (job #2818535) | Cod sursa (job #1876663) | Cod sursa (job #2578092) | Cod sursa (job #2976249) | Cod sursa (job #673214)
Cod sursa(job #673214)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define pb push_back
int n,m;
vector <int> vec[100003],ctc[100003];
stack <int> s;
int index[100003],lowlink[100003];
bool ok[100003];
int ct,nrctc;
void tarjan(int nod){
int i,w;
index[nod]=lowlink[nod]=ct;
ct++;
s.push(nod);
ok[nod] = 1;
for (i=0; i<vec[nod].size(); i++)
if (index[vec[nod][i]] == 999999){
tarjan(vec[nod][i]);
lowlink[nod] = min(lowlink[nod], lowlink[vec[nod][i]]);
}
else
if (ok[vec[nod][i]] == 1)
lowlink[nod] = min(lowlink[nod], index[vec[nod][i]]);
if (index[nod] == lowlink[nod]){
w = s.top();
ok[s.top()] = 0;
s.pop();
nrctc++;
ctc[nrctc].pb(w);
while (w != nod){
w = s.top();
ok[s.top()] = 0;
s.pop();
ctc[nrctc].pb(w);
}
}
}
int main()
{
int i,j,x,y;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for (i=1; i<=m; i++) {
f>>x>>y;
vec[x].pb(y);
}
for (i=1; i<=n; i++)
index[i] = lowlink[i] = 999999;
for (i=1; i<=n; i++)
if (index[i] == 999999)
tarjan(i);
g<<nrctc<<'\n';
for(i=1;i<=nrctc;i++){
for (j=0; j<(int)ctc[i].size(); j++)
g<<ctc[i][j]<<" ";
g<<'\n';
}
return 0;
}