Pagini recente » Cod sursa (job #120351) | Cod sursa (job #1943767) | Cod sursa (job #2358330) | Cod sursa (job #2137793) | Cod sursa (job #2524778)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int n , m , x , y;
vector < int > a[N] , b[N] , c[N];
stack < int > s;
short seen[N];
void dfs(int nod)
{
seen[nod] = 1;
for(int i = 0 ; i < a[nod].size() ; i++)
{
if(!seen[a[nod][i]])
dfs(a[nod][i]);
}
s.push(nod);
}
void dfst(int nod , int ctc)
{
seen[nod] = 2;
c[ctc].push_back(nod);
for(int i = 0 ; i < b[nod].size() ; i++)
{
if(seen[b[nod][i]] == 1)
dfst(b[nod][i] , ctc);
}
}
int main()
{
int i , j , ctc = 0;
f >> n >> m;
for(i = 1 ; i <= m ; i++)
{
f >> x >> y;
a[x].push_back(y);
b[y].push_back(x);
}
for(i = 1 ; i <= n ; i++)
if(!seen[i])
dfs(i);
while(!s.empty())
{
int nod = s.top();
if(seen[nod] == 1)
{
++ctc;
dfst(nod , ctc);
}
s.pop();
}
g << ctc << '\n';
for(i = 1 ; i <= ctc ; i++)
{
for(j = 0 ; j < c[i].size() ; j++)
g << c[i][j] << ' ';
g << '\n';
}
return 0;
}