Pagini recente » Cod sursa (job #1076313) | Cod sursa (job #2790566) | Cod sursa (job #2370433) | Cod sursa (job #1674391) | Cod sursa (job #698779)
Cod sursa(job #698779)
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100010
using namespace std;
stack<int>S;
vector<int>sol[MAXN],g[MAXN],gt[MAXN];
int m,n,ctc[MAXN],componente;
bool viz[MAXN];
void df(int x)
{
viz[x]=1;
for(int i=0;i<g[x].size();i++)
if(!viz[g[x][i]]) df(g[x][i]);
S.push(x);
}
void df2(int x)
{
ctc[x]=componente;
for(int i=0;i<gt[x].size();i++)
if(!ctc[gt[x][i]]) df2(gt[x][i]);
}
int main()
{
int i,j,x,y;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!viz[i]) df(i);
while(!S.empty())
{
while(!S.empty() and ctc[S.top()]) S.pop();
if(S.empty()) break;
x=S.top(); S.pop();
componente++;
df2(x);
}
fo<<componente<<"\n";
for(i=1;i<=n;i++) sol[ctc[i]].push_back(i);
for(i=1;i<=componente;i++)
{
for(j=0;j<sol[i].size();j++) fo<<sol[i][j]<<" ";
fo<<"\n";
}
return 0;
}