Pagini recente » Cod sursa (job #2939820) | Cod sursa (job #2298454) | Cod sursa (job #2180606) | Cod sursa (job #2596503) | Cod sursa (job #1971277)
#include <fstream>
#include <vector>
#include <algorithm>
#define nMax 100001
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, ind, nrctc;
int lev[nMax], low[nMax], viz[nMax];
vector<int> stck, ctc[nMax], G[nMax];
void tarjan(int node)
{
lev[node]=low[node]=++ind;
viz[node]=1;
stck.pb(node);
for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
{
int fiu=*it;
if(lev[fiu]==0)
{
tarjan(fiu);
low[node]=min(low[node], low[fiu]);
}
else
if(viz[fiu])
low[node]=min(low[node], low[fiu]);
}
if(low[node]==lev[node])
{
nrctc++;
int nodeAux;
do
{
nodeAux=stck.back();
viz[nodeAux]=0;
ctc[nrctc].pb(nodeAux);
stck.pop_back();
}
while(node!=nodeAux);
}
}
int main()
{
int a, b;
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>a>>b;
G[a].pb(b);
}
for(int i=1; i<=n; i++)
if(lev[i]==0)
tarjan(i);
fout<<nrctc<<'\n';
for(int i=1; i<=nrctc; i++)
{
for(vector<int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); it++)
fout<<*it<<" ";
fout<<'\n';
}
}