Pagini recente » Cod sursa (job #2063196) | Cod sursa (job #1853790) | Cod sursa (job #532566) | Cod sursa (job #829648) | Cod sursa (job #1172942)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int ctc,k,p,i,j,x,y,n,m;
int s[100010],viz[100010],low[100010];
vector <int> C[100010];
vector <int> l[100010];
int minim (int a, int b) {
if (a<b)
return a;
return b;
}
void dfs(int nod) {
viz[nod]=++k;
low [nod]=k;
s[++p]=nod;
for (int i=0;i<l[nod].size();i++) {
if (viz[l[nod][i]]==0)
dfs (l[nod][i]);
if (viz[l[nod][i]]>0)
low[nod]=minim(low[nod],low[l[nod][i]]);
}
if (low[nod]==viz[nod]){
ctc++;
while (s[p]!=nod){
C[ctc].push_back(s[p]);
p--;
}
C[ctc].push_back(nod);
p--;
}
}
int main () {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y;
l[x].push_back(y);
}
for (i=1;i<=n;i++)
if (viz[i]==0)
dfs(i);
fout<<ctc<<"\n";
for (i=1;i<=ctc;i++) {
for (j=0;j<C[i].size();j++) {
fout<<C[i][j]<<" ";
}
fout<<"\n";
}
return 0;
}