Pagini recente » Cod sursa (job #351365) | Cod sursa (job #1962070) | Cod sursa (job #1214683) | Cod sursa (job #2880791) | Cod sursa (job #2168952)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100005;
int dep[N], low[N], st[N], depth, nrCTC, stSize;
bool inStack[N];
vector <int> v[N], l[N];
void pushStack(int node){
st[++stSize] = node;
inStack[node] = true;
}
void newCTC(int ns){
nrCTC++;
do{
l[nrCTC].push_back(st[stSize]);
inStack[st[stSize]] = false;
}while(st[stSize--] != ns);
}
void tarjan(int ns){
int sz = v[ns].size(), nbr;
low[ns] = dep[ns] = ++depth;
pushStack(ns);
for(int i=0;i<sz;i++){
nbr = v[ns][i];
if(dep[nbr] == 0){
tarjan(nbr);
if(low[ns] > low[nbr])
low[ns] = low[nbr];
}
else if(inStack[nbr] && low[ns] > low[nbr])
low[ns] = low[nbr];
}
if(low[ns] == dep[ns])
newCTC(ns);
}
void print(){
int sz;
out<<nrCTC<<"\n";
for(int i=1;i<=nrCTC;i++){
sz = l[i].size();
for(int j=0;j<sz;j++)
out<<l[i][j]<<" ";
out<<"\n";
}
}
int main()
{
int n, m, x, y;
in>>n>>m;
for(int i=1;i<=m;i++){
in>>x>>y;
v[x].push_back(y);
}
in.close();
for(int i=1;i<=n;i++)
if(dep[i] == 0)
tarjan(i);
print();
out.close();
return 0;
}